LeetCode 139. 单词拆分
原题链接
中等
作者:
yxxxl7
,
2022-03-31 22:46:03
,
所有人可见
,
阅读 149
算法 动态规划 $O(n^2)$
- 状态表示 $f[i]$ 表示字符串S在[1, i]区间的字符可以在字典中匹配
- 状态转移:遍历区间[1 - i]这一段,f[i] = f[j] && S的[j - i]这一段在字典中存在 (0 <= j <= i)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
//优化查询,将字典中的所有字符串存到Set中
Set<String> set = new HashSet(wordDict);
boolean[] f = new boolean[n + 1];
//初始化f[0] = true
f[0] = true;
for(int i = 1; i <= n; i ++ ){
for(int j = i; j >= 0; j -- ){
if(f[j] && set.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[n];
}
}