计算字符串中最长的回文子串
Calculating longest Palindrome substring in the String
我有下面的代码来计算字符串中最长的回文子串。在线评委接受了O(n^2)的解,但我不知道为什么不接受我的解,虽然看起来我的算法复杂度是O(n^2)`
class Ideone {
public static void main(String args[]) {
Ideone ob = new Ideone();
String s = "sds";
System.out.println(ob.longestPalindrome(s));
}
public String longestPalindrome(String s) {
int maxlength = 1;
String ps = s.charAt(0) + "";
if (s.length() == 1)
return s;
for (int i = 0; i < s.length() - 1; i++) {
int j = (s.substring(i + 1)).indexOf(s.charAt(i)) + i + 1;
while (j < s.length() && j > i) {
if (j - i + 1 > maxlength && check(s.substring(i, j + 1))) {
maxlength = j - i + 1;
ps = s.substring(i, j + 1);
}
if ((s.substring(j + 1)).indexOf(s.charAt(i)) < 0) {
break;
}
j = (s.substring(j + 1)).indexOf(s.charAt(i)) + j + 1;
}
}
return ps;
}
public boolean check(String s) {
int l = s.length();
if (l == 1)
return false;
int t = l / 2;
String s1, s2;
if (l % 2 == 0) {
s1 = s.substring(0, t);
s2 = s.substring(t);
} else {
s1 = s.substring(0, t);
s2 = s.substring(t + 1);
}
s2 = (new StringBuffer(s2)).reverse().toString();
if (s1.compareTo(s2) == 0)
return true;
else return false;
}
}
初看两个循环和一个需要 O(n) 来反转字符串的方法 check() 可能会导致 O(n³)。
请注意以下方法:
- String.indexOf(..)
- String.substring(..)
- String.compareTo(..)
- StringBuffer.reverse(..)
- String.toString()
需要遍历数据,因此需要大约 O(n) 而不是常数时间。
看起来它需要的时间超过 O(n2)。下面是动态规划的程序代码.. 不是 java 但可以用作算法
http://www.geeksforgeeks.org/longest-palindromic-substring-set-2/
我有下面的代码来计算字符串中最长的回文子串。在线评委接受了O(n^2)的解,但我不知道为什么不接受我的解,虽然看起来我的算法复杂度是O(n^2)`
class Ideone {
public static void main(String args[]) {
Ideone ob = new Ideone();
String s = "sds";
System.out.println(ob.longestPalindrome(s));
}
public String longestPalindrome(String s) {
int maxlength = 1;
String ps = s.charAt(0) + "";
if (s.length() == 1)
return s;
for (int i = 0; i < s.length() - 1; i++) {
int j = (s.substring(i + 1)).indexOf(s.charAt(i)) + i + 1;
while (j < s.length() && j > i) {
if (j - i + 1 > maxlength && check(s.substring(i, j + 1))) {
maxlength = j - i + 1;
ps = s.substring(i, j + 1);
}
if ((s.substring(j + 1)).indexOf(s.charAt(i)) < 0) {
break;
}
j = (s.substring(j + 1)).indexOf(s.charAt(i)) + j + 1;
}
}
return ps;
}
public boolean check(String s) {
int l = s.length();
if (l == 1)
return false;
int t = l / 2;
String s1, s2;
if (l % 2 == 0) {
s1 = s.substring(0, t);
s2 = s.substring(t);
} else {
s1 = s.substring(0, t);
s2 = s.substring(t + 1);
}
s2 = (new StringBuffer(s2)).reverse().toString();
if (s1.compareTo(s2) == 0)
return true;
else return false;
}
}
初看两个循环和一个需要 O(n) 来反转字符串的方法 check() 可能会导致 O(n³)。
请注意以下方法:
- String.indexOf(..)
- String.substring(..)
- String.compareTo(..)
- StringBuffer.reverse(..)
- String.toString()
需要遍历数据,因此需要大约 O(n) 而不是常数时间。
看起来它需要的时间超过 O(n2)。下面是动态规划的程序代码.. 不是 java 但可以用作算法 http://www.geeksforgeeks.org/longest-palindromic-substring-set-2/