有意思的题目。。
其实可以用动态规划,但是输出稍微麻烦。
动规公式,设置a[i][j]为字符串从i到j的组合数
初始化a[i][j] = 0;
if(a[i][j] is a word)
a[i][j] = 1;
推导
for(int k=i;k<j;k++)
a[i][j] = a[i][j] + a[i][k] * a[k+1][j] ;
我这里用了递归,字符串str的word break,等于字符串str[0...i]的word break与字符串str[i+1....]的word break的组合。
如果用Trie来判定前缀的话,估计会更加快一点。
但是遇到一个案例aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab的时候我的算法也没辙,只好用个数组来记录哪些字符串是已经遍历失败过,不用再遍历。
Word Break II | Accepted | 440 ms | java |
import java.util.*; public class WordBreak2 { public ArrayList<String> wordBreak(String s, Set<String> dict) { Set<String> preDict = new HashSet<String>(); for (String tmps : dict) { for (int j = 0; j < tmps.length()-1; j++) preDict.add(tmps.substring(0, j+1)); } boolean[][] substrMap = new boolean[s.length()][s.length()]; for(int i=0;i<s.length();i++) for(int j=0;j<s.length();j++) substrMap[i][j] = true; ArrayList<String> result = SubWordBreak(s, 0, dict, preDict, substrMap); return result; } public ArrayList<String> SubWordBreak(String s, int beg, Set<String> dict, Set<String> preDict, boolean[][] substrMap) { ArrayList<String> result = new ArrayList<String>(); for (int j = beg; j < s.length(); j++) { if(j< s.length()-1 && substrMap[j+1][s.length()-1]==false) continue; String subStr = s.substring(beg, j + 1); if (dict.contains(subStr)) { if (j == s.length() - 1) { result.add(subStr); break; } else { ArrayList<String> subRes = SubWordBreak(s, j + 1, dict, preDict,substrMap); if (subRes.size() > 0) { for (String tmp : subRes) { result.add(subStr + " " + tmp); } } } } if (!preDict.contains(subStr)) { break; } } if(result.size() == 0) substrMap[beg][s.length()-1]=false; return result; } public static void main(String[] args) { WordBreak2 wb = new WordBreak2(); Set<String> dict = new HashSet<String>(); dict.add("cat"); dict.add("cats"); dict.add("and"); dict.add("sand"); dict.add("dog"); // dict.add("a"); // dict.add("aa"); // dict.add("aaa"); // dict.add("aaaa"); // dict.add("aaaaa"); // dict.add("aaaaaa"); // dict.add("aaaaaaa"); // dict.add("aaaaaaaa"); // dict.add("aaaaaaaaa"); // dict.add("aaaaaaaaaa"); // ArrayList<String> res = wb.wordBreak("catsanddog", dict); for (String tmps : res) System.out.println(tmps); } }