DP Trie¶
Table of Contents¶
- 139. Word Break (Medium)
- 140. Word Break II (Hard)
- 472. Concatenated Words (Hard)
- 2977. Minimum Cost to Convert String II (Hard)
139. Word Break¶
from typing import List
# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
for word in wordDict:
m = len(word)
if s[i - m : i] == word and dp[i - m]:
dp[i] = True
return dp[-1]
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) # True
#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int max_len = ranges::max(wordDict, {}, &string::length).length();
unordered_set<string> words(wordDict.begin(), wordDict.end());
int n = s.length();
vector<int> f(n + 1);
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j >= max(i - max_len, 0); j--) {
if (f[j] && words.count(s.substr(j, i - j))) {
f[i] = true;
break;
}
}
}
return f[n];
}
};
int main() {
Solution solution;
string s = "leetcode";
vector<string> wordDict = {"leet", "code"};
assert(solution.wordBreak(s, wordDict) == true);
return 0;
}
140. Word Break II¶
-
Tags: Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization