題目網址：https://leetcode.cn/problems/word-break/
題意：給一 string s 和一 string list wordDict, 若 wordDict 中的單字能組出 s 則返回 true。
注意：wordDict 中的 string 互不相同, 且 s.length ≤ 300
Solution 1：
想法：利用 DP, 其中 dp[i] 代表 s[0~(i-1)] 是否能被拆分成若干個出現在 wordDict 中的單字, 我們要枚舉 s[0~(i-1)] 中的切割點 j, 使得 s[0~(j-1)] 和 s[j~(i-1)] 皆在 wordDict 中, 由於 j < i, 所以要計算 dp[i] 時可透過先前計算過的 d[j] 知道 s[0~j] 是否能被拆分, 然後再判斷 s[j~(i-1)] 是否在 wordDict 中即可, 故得到以下公式：
dp[i] = dp[j] && check(s[j~(i-1)])check(s[j~(i-1)]) 代表檢查 s[j~(i-1)] 是否在 wordDict 中
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
const int n = s.size();
vector<bool> dp(n + 1, false);
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
dp[0] = true;
for (int i = 1; i <= n; ++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.back();
}
};
|
- time：$O(n^2)$ ➔ for loop
- space：$O(n)$ ➔
dp
Solution 2：（TLE 無法通過）
想法：利用 DFS + Trie
class TrieNode{
public:
TrieNode* children[26] = {nullptr};
bool isEnd = false;
};
class Trie{
public:
TrieNode *root;
Trie() : root(new TrieNode()) {}
void insert(const string& word){
TrieNode *node = root;
for (const auto& ch : word) {
const int i = ch - 'a';
if (!node->children[i]) {
node->children[i] = new TrieNode();
}
node = node->children[i];
}
node->isEnd = true;
}
};
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
for (const auto& word : wordDict) {
trie.insert(word);
}
return dfs(s, 0);
}
private:
Trie trie;
bool dfs(const string& s, const int cur){
if (cur == s.size()) {
return true;
}
TrieNode *node = trie.root;
for (int i = cur; i < s.size(); ++i) {
const int idx = s[i] - 'a';
if (node->children[idx]) {
node = node->children[idx];
if (node->isEnd && dfs(s, i + 1)) {
return true;
}
} else {
break;
}
}
return false;
}
};
|
time：$O(\sum_{i = 0}^{m-1}{w_i} + 2^n)$, 其中 $m$ 為 wordDict 中單字的個數, $w_i$ 為 wordDict[i] 的長度, $n$ 為 s 的長度
space：$O(\sum_{i = 0}^{m-1}{w_i})$ ➔ $O(26 \cdot \sum_{i = 0}^{m-1}{w_i})$, worse case：trie 中所有單字都沒有重複的 prefix
Solution 3：
想法：利用 DFS + Trie + DP, 改進 Solution 2, 若 s 中 idx = cur 為開頭往後的 substring 無法由若干個 wordDict[i] 所組成, 則透過 memo 紀錄起來, 藉此來進行 pruning, 避免重複走失敗的道路
class TrieNode{
public:
TrieNode* children[26] = {nullptr};
bool isEnd = false;
};
class Trie{
public:
TrieNode *root;
Trie() : root(new TrieNode()) {}
void insert(const string& word){
TrieNode *node = root;
for (const auto& ch : word) {
const int i = ch - 'a';
if (!node->children[i]) {
node->children[i] = new TrieNode();
}
node = node->children[i];
}
node->isEnd = true;
}
};
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
for (const auto& word : wordDict) {
trie.insert(word);
}
return dfs(s, 0);
}
private:
Trie trie;
bool memo[300] = {false};
bool dfs(const string& s, const int cur){
if (cur == s.size()) {
return true;
}
if (memo[cur] == true) {
return false;
}
TrieNode *node = trie.root;
for (int i = cur; i < s.size(); ++i) {
const int idx = s[i] - 'a';
if (node->children[idx]) {
node = node->children[idx];
if (node->isEnd && dfs(s, i + 1)) {
return true;
}
} else {
break;
}
}
memo[cur] = true;
return false;
}
};
|
- time：$O(\sum_{i = 0}^{m-1}{w_i} + n^2)$, 其中 $m$ 為
wordDict 中單字的個數, $w_i$ 為 wordDict[i] 的長度, $n$ 為 s 的長度
- $O(\sum_{i = 0}^{m-1}{w_i})$：將
wordDict 中每個單字 insert 到 trie 中
- $O(n^2)$：判斷長度為
n 的 s 能否拆分成其他單字
- $O(n^2)$ : $T(n) = T(n - 1) + O(n)$, 因為有用
memo 記憶, 所以呼叫 $T(n-1)$ 即可, 因為 $T(n-1)$ 會再往下呼叫 $T(n-2)$, 依此類推 …, 每個 $T(n-i)$ 只要呼叫一次即可（因為會記住結果）。
- $O(n)$ 是因為呼叫一次 $T(n-1)$ 後, 剩下 $T(n-2), …, T(1)$ 都會計算出來。原本 $O(n)$ 應寫作 $T(n-2) + T(n-3) + … +T(1)$, 但是除了 $T(n-1)$, 剩下的 $T(n-i)$ 都只需 $O(1)$, 故 $T(n-2) + T(n-3) + … +T(1)$ 可直接寫成 $O(n)$。
- space：$O(\sum_{i = 0}^{m-1}{w_i})$ ➔ $O(26 \cdot \sum_{i = 0}^{m-1}{w_i})$ + $O(1)$
- $O(26 \cdot \sum_{i = 0}^{m-1}{w_i})$：worse case：trie 中所有單字都沒有重複的 prefix
- $O(1)$：
memo 為常數空間
