给定一个 dict, 里面是valid words.
再给定一个 String, 将String split 为 dict 中 valid words 的划分方法。
例如:
dict = {"one", "search", "for", "all" , "results"};
str = "oneforall";
对 str 一种划分方法就是: one, for, all
这里的思路是使用 trie tree 进行前缀搜索
public ArrayList<String> splitValidWords(String str, TrieNode dict) {
ArrayList<String> result = new ArrayList<String>();
if (str == null || str.length() == 0 || dict == null) {
return result;
}
splitHelper(str, dict, result);
return result;
}
public boolean splitHelper(String str, TrieNode dict, ArrayList<String> result) {
if (str == null || str.length() == 0) {
return true;
}
TrieNode n = dict;
for (int i = 0; i < str.length(); i++) {
int k = str.charAt(i) - 'a';
if (n.childNodes[k].validWord) {
result.add(str.substring(0, i + 1));
if (splitHelper(str.subString(i + 1), dict, result)) {
break;
} else {
result.remove(result.size() - 1);
}
result.remove(result.size() - 1);
n = n.childNodes[k];
} else {
n = n.childNodes[k];
}
}
}
public class TrieNode {
String nodeString;
TrieNode[] childNodes;
int count;
boolean validWord;
public TrieNode() {
childNodes = new TrieNode[26];
count = 0;
nodeString = "";
}
}