[leetcode] Word Break II

这题DFS的话会有很多重复计算分支
所以参照Word Break 里面的lookup, 先建一个table 来知道 那段是有solution的 才DFS进去
这里是从string尾部开始做DFS的

*其实我觉得还可以更加快。。就是建一个hashtable 然后bottom up 上去 可以进一步减少DFS的次数，下一pass的时候 试下吧

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class Solution { boolean[] lookup; List<String> result = new ArrayList<String>(); public List<String> wordBreak(String s, Set<String> wordDict) { if (s.length() == 0){ return result; } constructLookup(s, wordDict); dfs(s, wordDict, s.length()-1, ""); return result; } private void dfs(String s, Set<String> wordDict, int currentIndex, String strFromUpper){ if (wordDict.contains((s.substring(0, currentIndex+1)))){ result.add(s.substring(0, currentIndex+1)+strFromUpper); } for(int i = currentIndex; i >= 1; i--){ if (lookup[i-1] && wordDict.contains(s.substring(i, currentIndex+1))){ String tempStr = " "+s.substring(i, currentIndex+1)+strFromUpper; dfs(s, wordDict, i-1, tempStr); } } } private void constructLookup(String s, Set<String> wordDict){ lookup = new boolean[s.length()]; if (wordDict.contains(s.substring(0,1))){ lookup[0] = true; } for (int i = 1; i < s.length(); i++){ lookup[i] = wordDict.contains(s.substring(0, i+1)); for (int j = i-1; j >= 0 && !lookup[i]; j--){ lookup[i] = lookup[j] && wordDict.contains(s.substring(j+1, i+1)); } } return; } }