题目描述
分析
1. 循环+记录已匹配的单词位
代码实现
public enum Q139 {
instance;
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
// 上次配置的单词是true
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
public static void main(String[] args) {
// assert true
System.out.println(Q139.instance.wordBreak("abc", Lists.newArrayList("abc","aaa")));
// assert true
System.out.println(Q139.instance.wordBreak("applepenapple", Lists.newArrayList("apple", "pen")));
// assert false
System.out.println(Q139.instance.wordBreak("catsandog", Lists.newArrayList("cats", "dog", "sand", "and", "cat")));
// assert false
System.out.println(Q139.instance.wordBreak("a", Lists.newArrayList("b")));
// assert true
System.out.println(Q139.instance.wordBreak("a", Lists.newArrayList("a")));
// assert true
System.out.println(Q139.instance.wordBreak("aaaaaaa", Lists.newArrayList("aaaa","aaa")));
}
}
The More intensive life is,the greater vitality it will present. (Germany) Engels
生活越紧张，越能显示人的生命力。– [德] 恩格斯
