c********p
发帖数: 1969 | 1 请大牛帮忙看看。
第一个是longest palindrome的，我按leetcode discussion的c++代码改的java的，怎
么就过不了了呢？一行行对过了阿。。。我知道有o(n)的算法，但这个dp的我就奇怪怎
么过不了呢，哪个细节写错了。。。
public class Solution {
public String longestPalindrome(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || s.length() <= 1){
return s;
}
int[][] P = new int[s.length()][s.length()];
int max = 1;
int begin = 0;
for(int i = 0; i < s.length(); i++){
P[i][i] = 1;
}
for(int i = 0; i < s.length() - 1; i++){
if(s.charAt(i) == s.charAt(i + 1)){
P[i][i + 1] = 1;
max = 2;
begin = i;
}
}
for(int L = 3; L <= s.length(); L++){
for(int i = 0; i < s.length() - L + 1; i++){
int j = i + L - 1;
if(s.charAt(i) == s.charAt(j) && P[i + 1][j - 1] == 1){
P[i][j] = 1;
max = L;
begin = i;
}
}
}
return s.substring(begin, begin + max);
}
}
第2个是 palindrome partition ii
是因为我用了2维的数组么？也过不了大oj。
public class Solution {
public int minCut(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || s.length() == 0){
return 0;
}
int[][] P = new int[s.length()][s.length()];
int[][] C = new int[s.length()][s.length()];
for(int i = 0; i < s.length(); i++){
P[i][i] = 1;
C[i][i] = 0;
}
for(int L = 2; L <= s.length(); L++){
for(int i = 0; i < s.length() - L + 1; i++){
int j = i + L - 1;
if(i == j - 1){
if(s.charAt(i) == s.charAt(j)){
P[i][j] = 1;
}else{
P[i][j] = 0;
}
}else{
if(s.charAt(i) == s.charAt(j) && P[i + 1][j - 1] == 1){
P[i][j] = 1;
}else{
P[i][j] = 0;
}
}
if(P[i][j] == 1){
C[i][j] = 0;
}else{
C[i][j] = Integer.MAX_VALUE;
for(int k = i; k < j; k++){
C[i][j] = Math.min(C[i][j], C[i][k] + C[k + 1][j] +
1);
}
}
}
}
return C[0][s.length() - 1];
}
}
谢谢大家帮忙！ |
|
