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在每一位是否存在可能解。在继续递归之前，把当前的解集存一下，递归之后，解集没有改变，说明没有继续执行的必要。
实现代码：
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<string> WordBreak(string s, ISet<string> wordDict)
{
var results = new List<string>();
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<string> wordDic, string result, IList<string> 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;
}
}
}
}
}