139. Word Break
給定一個字符串 s 和一個字符串字典 wordDict，如果 s 可以被分割成一個或多個字典中的單詞組成的以空格分隔的序列，則返回 true。
注意：字典中的同一個單詞在分割中可以多次重用。
範例：
輸入：s = "leetcode", wordDict = ["leet","code"] 輸出：true 解釋：返回 true 因為 "leetcode" 可以被分割為 "leet code"。
Python
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
16.74MB, 45ms
C++
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.length() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.length(); ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
};
15.92MB, 11ms
Javascript
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
};
51.74MB, 11ms
