class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
}
};
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s 和 wordDict[i] 仅有小写英文字母组成wordDict 中的所有字符串 互不相同相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2021-07-26 22:02:09
func wordBreak(s string, wordDict []string) bool {
mp := make(map[string]bool)
for _, word := range wordDict {
mp[word] = true
}
dp := make([]bool, len(s)+1)
dp[0] = true
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
if dp[j] && mp[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[len(s)]
}
python3 解法, 执行用时: 40 ms, 内存消耗: 13.8 MB, 提交时间: 2020-11-19 02:24:06
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
import functools
@functools.lru_cache(None)
def back_track(s):
if(not s):
return True
res=False
for i in range(1,len(s)+1):
if(s[:i] in wordDict):
res=back_track(s[i:]) or res
return res
return back_track(s)
python3 解法, 执行用时: 44 ms, 内存消耗: 13.6 MB, 提交时间: 2020-11-19 02:21:55
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[0] = True
for i in range(0, n):
for j in range(i+1, n+1):
if dp[i] and s[i:j] in wordDict:
dp[j] = True
return dp[-1]
python3 解法, 执行用时: 64 ms, 内存消耗: 13.6 MB, 提交时间: 2020-11-19 02:02:53
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[0] = True
for i in range(1, n+1):
for j in range(0, i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[n]