dp/word-break
优质
小牛编辑
123浏览
2023-12-01
Word Break
描述
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode"
,
dict = ["leet", "code"]
.
Return true because "leetcode"
can be segmented as "leet code"
.
分析
本题最直观的做法是 BFS,也可以用 DFS 和动态规划。
代码
DFS
// Word Break
// 深搜,超时
// 时间复杂度O(2^n),空间复杂度O(n)
class Solution {
public boolean wordBreak(String s, Set<String> dict) {
return dfs(s, dict, 0, 1);
}
private static boolean dfs(String s, Set<String> dict,
int start, int cur) {
if (cur == s.length()) {
return dict.contains(s.substring(start, cur));
}
if (dfs(s, dict, start, cur+1)) return true; // no cut
if (dict.contains(s.substring(start, cur))) // cut here
if (dfs(s, dict, cur+1, cur+1)) return true;
return false;
}
}
// Word Break
// 深搜,超时
// 时间复杂度O(2^n),空间复杂度O(n)
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
return dfs(s, dict, 0, 1);
}
private:
static bool dfs(const string &s, unordered_set<string> &dict,
size_t start, size_t cur) {
if (cur == s.size()) {
return dict.find(s.substr(start, cur-start)) != dict.end();
}
if (dfs(s, dict, start, cur+1)) return true; // no cut
if (dict.find(s.substr(start, cur-start)) != dict.end()) // cut here
if (dfs(s, dict, cur+1, cur+1)) return true;
return false;
}
};
BFS
// Word Break
// BFS
// Time Complexity: O(n^2), Space Complexity: O(n)
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[s.length()];
queue.offer(0);
while (!queue.isEmpty()) {
int start = queue.poll();
if (!visited[start]) {
for (int end = start + 1; end <= s.length(); end++) {
if (set.contains(s.substring(start, end))) {
queue.offer(end);
if (end == s.length()) {
return true;
}
}
}
visited[start] = true;
}
}
return false;
}
}
// TODO
动规
设状态为f(i)
,表示s[0,i)
是否可以分词,则状态转移方程为
f(i) = any_of(f(j) && s[j,i] in dict), 0 <= j < i
// Word Break
// 动规,时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public boolean wordBreak(String s, Set<String> dict) {
// 长度为n的字符串有n+1个隔板
boolean[] f = new boolean[s.length() + 1];
f[0] = true; // 空字符串
for (int i = 1; i <= s.length(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.contains(s.substring(j, i))) {
f[i] = true;
break;
}
}
}
return f[s.length()];
}
}
// Word Break
// 动规,时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
// 长度为n的字符串有n+1个隔板
vector<bool> f(s.size() + 1, false);
f[0] = true; // 空字符串
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
}
};