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"].
解题思路：
参考上题思路二的解法，修改下代码，让其显示路径即可，JAVA实现如下：
static public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> list = new ArrayList<String>();
dfs(list, s, wordDict, new HashSet<String>(), new ArrayList<String>());
return list;
}
static public boolean dfs(List<String> list, String s, Set<String> dict,
Set<String> unmatch, List<String> alist) {
boolean isMatch=false;
for (String prefix : dict) {
if (s.equals(prefix)) {
alist.add(prefix);
StringBuilder sb = new StringBuilder();
for (String str : alist) {
sb.append(str);
sb.append(" ");
}
list.add(sb.substring(0, sb.length() - 1));
alist.remove(alist.size() - 1);
isMatch=true;
continue;
} else if (s.startsWith(prefix)) {
String suffix = s.substring(prefix.length());
if (!unmatch.contains(suffix)) {
alist.add(prefix);
if (!dfs(list, suffix, dict, unmatch, alist))
unmatch.add(suffix);
else isMatch=true;
alist.remove(alist.size() - 1);
}
}
}
return isMatch;
}