public class Solution {
// f[i] - if s.substring(0, i) can be segmented
// f[i] = f[j] && wordDict.contains(s.substring(j, i))
// f[0] = true
// result - f[s.length()]
public boolean wordBreak(String s, Set wordDict) {
if (s == null || s.length() == 0) {
return true;
}
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for (int i = 1; i <= s.length(); i++) {
f[i] = false;
for (int j = 0; j < i; j++) {
f[i] = f[i] || (f[j] && wordDict.contains(s.substring(j, i)));
}
}
return f[s.length()];
}
}
2016年7月31日星期日
[LeetCode] #139 Word Break
订阅:
博文评论 (Atom)
没有评论:
发表评论