j*****y
发帖数: 1071 | 1 过不了大的 case阿，
dp好像也快不了多少阿
dp[i] = min_cut for s[0,...,i] |
a***o
发帖数: 1182 | 2 dp + dp...
【在 j*****y 的大作中提到】
: 过不了大的 case阿，
: dp好像也快不了多少阿
: dp[i] = min_cut for s[0,...,i]
|
p*****2
发帖数: 21240 | 3
http://blog.sina.com.cn/s/blog_b9285de20101iwqt.html
【在 j*****y 的大作中提到】
: 过不了大的 case阿，
: dp好像也快不了多少阿
: dp[i] = min_cut for s[0,...,i]
|
j*****y
发帖数: 1071 | |
j*****y
发帖数: 1071 | 5 thanks.
【在 a***o 的大作中提到】
: dp + dp...
|
B********t
发帖数: 147 | 6 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
变总的时间复杂度
class Solution {
public:
bool isPalindrome(string s)
{
int start = 0, end = s.size() - 1;
while(start < end)
if(s[start++] != s[end--])
return false;
return true;
}
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector dp(s.size(), INT_MAX);
vector> isValid(s.size(), vector(s.size(), false)
);
for(int i = 0; i < s.size(); i++)
{
if(isPalindrome(s.substr(0, i+1)))
{
dp[i] = 0;
isValid[0][i] = true;
continue;
}
else
for(int j = 1; j <= i; j++)
if(s[i] == s[j] && (j+2 > i || isValid[j+1][i-1]))
{
isValid[j][i] = true;
dp[i] = min(dp[i], dp[j-1]+1);
}
}
return dp[s.size()-1];
}
};
【在 j*****y 的大作中提到】
: thanks.
|
c********t
发帖数: 5706 | 7 baby, 这题你不是做过的吗？
【在 B********t 的大作中提到】
: 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
: 变总的时间复杂度
: class Solution {
: public:
: bool isPalindrome(string s)
: {
: int start = 0, end = s.size() - 1;
: while(start < end)
: if(s[start++] != s[end--])
: return false;
|
B********t
发帖数: 147 | 8 我第一次写的是n^3的。话说上面代码里第一次判断palindrome能dp不。。
【在 c********t 的大作中提到】
: baby, 这题你不是做过的吗？
|
j*****y
发帖数: 1071 | 9 过不了大的 case阿，
dp好像也快不了多少阿
dp[i] = min_cut for s[0,...,i] |
a***o
发帖数: 1182 | 10 dp + dp...
【在 j*****y 的大作中提到】
: 过不了大的 case阿，
: dp好像也快不了多少阿
: dp[i] = min_cut for s[0,...,i]
|
|
|
p*****2
发帖数: 21240 | 11
http://blog.sina.com.cn/s/blog_b9285de20101iwqt.html
【在 j*****y 的大作中提到】
: 过不了大的 case阿，
: dp好像也快不了多少阿
: dp[i] = min_cut for s[0,...,i]
|
j*****y
发帖数: 1071 | |
j*****y
发帖数: 1071 | 13 thanks.
【在 a***o 的大作中提到】
: dp + dp...
|
B********t
发帖数: 147 | 14 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
变总的时间复杂度
class Solution {
public:
bool isPalindrome(string s)
{
int start = 0, end = s.size() - 1;
while(start < end)
if(s[start++] != s[end--])
return false;
return true;
}
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector dp(s.size(), INT_MAX);
vector> isValid(s.size(), vector(s.size(), false)
);
for(int i = 0; i < s.size(); i++)
{
if(isPalindrome(s.substr(0, i+1)))
{
dp[i] = 0;
isValid[0][i] = true;
continue;
}
else
for(int j = 1; j <= i; j++)
if(s[i] == s[j] && (j+2 > i || isValid[j+1][i-1]))
{
isValid[j][i] = true;
dp[i] = min(dp[i], dp[j-1]+1);
}
}
return dp[s.size()-1];
}
};
【在 j*****y 的大作中提到】
: thanks.
|
c********t
发帖数: 5706 | 15 baby, 这题你不是做过的吗？
【在 B********t 的大作中提到】
: 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
: 变总的时间复杂度
: class Solution {
: public:
: bool isPalindrome(string s)
: {
: int start = 0, end = s.size() - 1;
: while(start < end)
: if(s[start++] != s[end--])
: return false;
|
B********t
发帖数: 147 | 16 我第一次写的是n^3的。话说上面代码里第一次判断palindrome能dp不。。
【在 c********t 的大作中提到】
: baby, 这题你不是做过的吗？
|
f*****e
发帖数: 2992 | 17 感觉回文不用dp会更快。以每个letter/缝为中心向两边扫，也O(N^2)。不过不用全部
都扫到。
【在 j*****y 的大作中提到】
: 太厉害了，回文也用dp判断
|
a*******3
发帖数: 27 | 18
re，枚举中心点是回文O(n^2)算法中最好写，而且是最省空间的。不过要注意回文的长
度可能是奇数也可能是偶数的。
【在 f*****e 的大作中提到】
: 感觉回文不用dp会更快。以每个letter/缝为中心向两边扫，也O(N^2)。不过不用全部
: 都扫到。
|
c********t
发帖数: 5706 | 19 把 for(int j = 1; j <= i; j++)
改成 for(int j=i; j>=0; j--)
第一次判断palindrome还需要吗？
【在 B********t 的大作中提到】
: 我第一次写的是n^3的。话说上面代码里第一次判断palindrome能dp不。。
|
B********t
发帖数: 147 | 20 好嗒。。我想想
【在 c********t 的大作中提到】
: 把 for(int j = 1; j <= i; j++)
: 改成 for(int j=i; j>=0; j--)
: 第一次判断palindrome还需要吗？
|
|
|
j*****y
发帖数: 1071 | 21 有道理.
【在 f*****e 的大作中提到】
: 感觉回文不用dp会更快。以每个letter/缝为中心向两边扫，也O(N^2)。不过不用全部
: 都扫到。
|
r*****a
发帖数: 421 | 22 写了一个向两边扫的。
public int minCut(String s) {
int len = s.length();
int[] dp = new int[len];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i< len; ++i) {
for (int j = i-1; j <= i; j++) {
int start = i-1;
int end = j;
while (start >= 0 && end <= len-1 && s.charAt(start) == s.charAt(end))
{
if (start == 0) dp[end] = 0;
else
dp[end] = Math.min(dp[end], dp[start-1] + 1);
start--;
end++;
}
}
if (dp[i] > dp[i-1] + 1) dp[i] = dp[i-1] + 1;
}
return dp[len-1];
} |
j********r
发帖数: 25 | 23 参考了大牛们的， 写了一个自认为还算简洁的：
int minCut(string s) {
int m = s.length();
vector> palindromes(m, vector(m, false));
vector cuts(m,m);
cuts[0] = 0;
for(int i = 1; i < m; i++) {
for(int j = i; j >= 0; j--) {
if (s[i] == s[j] && (i-j <2 || palindromes[i-1][j+1])){
palindromes[i][j] = true;
if (j==0)
cuts[i] = 0;
else
cuts[i] = min(cuts[i], cuts[j-1]+1);
}
}
}
return cuts[m-1];
}
【在 r*****a 的大作中提到】
: 写了一个向两边扫的。
: public int minCut(String s) {
: int len = s.length();
: int[] dp = new int[len];
: Arrays.fill(dp, Integer.MAX_VALUE);
: dp[0] = 0;
:
: for (int i = 1; i< len; ++i) {
: for (int j = i-1; j <= i; j++) {
: int start = i-1;
|
T*******e
发帖数: 4928 | 24 similar, C++ DP version.
int minCut(string s) {
int sSize=s.size();
if(sSize<2) return 0;
vector minCuts(sSize+1,0);
for(int i=0; i<=sSize; ++i) minCuts[i]=sSize-1-i;
vector > isPalindrome(sSize, vector(sSize, false));
for(int i=sSize-2; i>=0; --i) {
for(int j=i; j
if(s[i]==s[j] && (j-i<=2 ||isPalindrome[i+1][j-1])) {
isPalindrome[i][j]=true;
minCuts[i]=min(minCuts[i],minCuts[j+1]+1);
}
}
}
return minCuts[0];
} |
j********r
发帖数: 25 | 25 真是不比不知道， 你这个又比我的少了个if check！
【在 T*******e 的大作中提到】
: similar, C++ DP version.
: int minCut(string s) {
: int sSize=s.size();
: if(sSize<2) return 0;
: vector minCuts(sSize+1,0);
: for(int i=0; i<=sSize; ++i) minCuts[i]=sSize-1-i;
: vector > isPalindrome(sSize, vector(sSize, false));
: for(int i=sSize-2; i>=0; --i) {
: for(int j=i; j: if(s[i]==s[j] && (j-i<=2 ||isPalindrome[i+1][j-1])) {
|
T*******e
发帖数: 4928 | 26 咱们差不多。我的比你多了一步initialization.
【在 j********r 的大作中提到】
: 真是不比不知道， 你这个又比我的少了个if check！
|
