LeetCode139——单词拆分
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接: https://leetcode-cn.com/problems/word-break/description/
题目描述:
知识点:动态规划
思路:动态规划
状态定义:
f(x, y) -------- s中范围在[x, y]内的子串能否被被空格拆分为一个或多个在字典中出现的单词
状态转移:
(1)如果s中范围在[x, y]内的子串出现在字典中,此时显然有f(x, y) = true。
(2)如果s中范围在[x, y]内的子串未出现在字典中,那么我们需要去看s中范围在[x, j]和[j + 1, y],j = x, ..., y内的两个子串是否能被拆分,一旦发现两个子串均能被拆分的情况,就判定f(x, y) = true。否则f(x, y) = false。
时间复杂度是O(mn ^ 2),其中m为wordDist中单词的数量,n为字符串s的长度。空间复杂度是O(n ^ 2)。
JAVA代码:
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[][] results = new boolean[n][n];
for (int i = 0; i < n; i++) {
results[i][i] = include(s.substring(i, i + 1), wordDict);
}
for (int gap = -1; gap >= - n + 1; gap--) {
for (int i = 0; i <= gap + n - 1; i++) {
results[i][i - gap] = include(s.substring(i, i - gap + 1), wordDict);
if(!results[i][i - gap]) {
for (int j = 0; j < - gap; j++) {
if(results[i][i + j] && results[i + j + 1][i - gap]) {
results[i][i - gap] = true;
break;
}
}
}
}
}
return results[0][n - 1];
}
private boolean include(String string, List<String> wordDict) {
for (String s : wordDict) {
if(s.equals(string)) {
return true;
}
}
return false;
}
}
LeetCode解题报告:
CSDN-Ada助手: 多亏了你这篇博客, 解决了问题: https://ask.csdn.net/questions/8028919, 请多输出高质量博客, 帮助更多的人
有点呆呆的: 感谢思路讲解,终于懂了
oXingXingHuo12: [code=plain] class Solution { public: string shortestPalindrome(string s) { string s_rev(s.rbegin(), s.rend()); string s_new = s + "#" + s_rev; int n = s_new.size(); vector<int> next(n, 0); for (int i = 1; i < n; i++) { int j = next[i - 1]; while (j > 0 && s_new[i] != s_new[j]) { j = next[j - 1]; } if (s_new[i] == s_new[j]) { j++; } next[i] = j; } return s_rev.substr(0, s.size() - next[n - 1]) + s; } }; [/code]
我从远处聆听你: 来感谢博主,上午49,下午53,过了
m0_60592258: 有python代码吗