LeetCode -- WordBreak II

LeetCode -- WordBreak II

題目描述：


Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.


Return all such possible sentences.


For example, given
s = catsanddog,
dict = [cat, cats, and, sand, dog].


A solution is [cats and dog, cat sand dog].




給定1個字符串s，和一個字典（字符串數組），對s進行分詞，求出所有可能情況。


從題目本身來看，本題的解法是一個DFS，拿到s.substr[0...n],如果在dic中存在，則拿到當前index對s.substr[index...n]遞歸執行，如果s在dic中找到，添加到結果集。 由於沒有剪枝，存在很多不必要的遞歸。


剪枝：可以使用長度為s.Length的數組來存放s在每一位是否存在可能解。在繼續遞歸之前，把當前的解集存一下，遞歸之後，解集沒有改變，說明沒有繼續執行的必要。




實現代碼：

public IList WordBreak(string s, ISet wordDict) 
   {
		var results = new List();
		var possible = new bool[s.Length];
		for(var i = 0;i < possible.Length; i++){
			possible[i] = true;
		}
		
		DfsWithCut(0,s, wordDict, , results, possible);
		return results;
   }


public void DfsWithCut(int start , string s, ISet wordDic, string result, IList results, bool[] possible){


	var left = s.Substring(start , s.Length - start);
	if(wordDic.Any(x=> x == left)){
		var r = result ==  ? left : result +   + left;
		results.Add(r);
	}
	
   for(var i = start ;i < s.Length ; i++){
       var w = s.Substring(start, i - start + 1);


       if(wordDic.Any(x=>x == w) && i < s.Length - 1){
           if(possible[i+1] /*only if possible do recursion*/){
		       var r = result ==  ? w : result +   + w;
			   var before = results.Count; // track current results count before dfs
               DfsWithCut(i + 1, s , wordDic, r, results, possible);
			   if(results.Count == before){ // since no new result found , mark possible[i+1] as false to cut it
			   		possible[i+1] = false;
			   }
           }
		   
       }
   }
   
}