/*
* @lc app=leetcode id=139 lang=cpp
*
* [139] Word Break
*/
// @lc code=start
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
const int N = s.size();
int mx_len = 0;
for (const auto w : wordDict) {
mx_len = max((int)w.length(), mx_len);
}
vector<bool> dp(N + 1, false);
dp[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = max(i - 1 - mx_len, 0); j < i; ++j) {
if (dp[j] && words.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[N];
}
};
// @lc code=end
public class Solution {
/**
* @param s: A string s
* @param dict: A dictionary of words dict
*/
public boolean wordBreak(String s, Set<String> dict) {
int n = s.length();
// init
boolean[] f = new boolean[n + 1];
f[0] = true; // empty, 前0个
int maxLen = 0;
for (String str : dict) {
maxLen = Math.max(maxLen, str.length());
}
// loop
for (int i = 1; i <= n; i++) {
for (int j = Math.max(0, i - maxLen); j < i; j++) {
if (f[j] && dict.contains(s.substring(j, i))) {
f[i] = true;
break;
}
}
}
return f[n];
}
}