给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词
https://leetcode-cn.com/problems/word-break/
示例1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
Java解法
思路:
初步考虑用递归处理,每次拆分当中的某个单词,拆分剩下的继续拆分,直到无法完成拆分,
static List<List<Boolean>> results = new ArrayList<>(); public static boolean wordBreak(String s, List<String> wordDict) { wordBreak2(s, wordDict, new ArrayList<>()); for (List<Boolean> aBoolean : results) { if (aBoolean.contains(true)) { return true; } } return false; } public static void wordBreak2(String s, List<String> wordDict, List<Boolean> booleans) { for (String word : wordDict) { int i = s.indexOf(word); if (i != -1) { String substring = s.replaceFirst(word,"-"); if (substring.replaceAll("-","").equals("")) { booleans.add(true); results.add(booleans); return; } wordBreak2(substring, wordDict, new ArrayList<>(booleans)); } } booleans.add(false); results.add(booleans); }
但效率不行,超出时间限制了
参考官方解:动态规划
思考的过于复杂了,遍历出上一个位置可能存在的解,判断后方新增是否被包含即可完成判断
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++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
image
官方解
https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/
-
动态规划
官方解牛逼!算法比解释更易懂
- 时间复杂度:O(n^2)
- 空间复杂度:O(n^2)
网友评论