计算字符串中最长的回文子字符串

我有以下代码来计算字符串中最长的回文子字符串。在线法官接受为O（n^2）解决方案，但我不知道它为什么不接受我的解决方案虽然看上去我的算法是O（n^2）complexity.`计算字符串中最长的回文子字符串

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; 
    } 

}

来源

2017-05-29 Rishabh Nigam

检查你的代码是否为0（n²）？创建一个表并绘制运行时间图。 – MrSmith42

在第一瞥见两个循环，并且需要O（n）反转字符串的方法check（）可能会导致O（n³）。

要知道，类似的方法：

String.indexOf（..）
String.substring（..）
String.compareTo（..）
StringBuffer.reverse（ ..）
String.toString（）

需要通过数据进行迭代，因此NE编辑约O（n）而不是恒定的时间。

来源

2017-05-29 11:09:17 MrSmith42

非常感谢。这对我有用。现在我能够弄清楚为什么我的算法没有被接受。 –

reverse（）不是String的函数，而是StringBuffer ..我想澄清一下，如果子字符串也需要线性时间吗？因为我认为它是一个常量时间函数吗？如果我错了，请纠正我的错误..提前提示 –

@ Rishabh Nigam：根据子字符串的实现，子字符串的大小至少是线性的，因为这些数据被复制来创建新的实例。我的回答不是要列出昂贵的方法的完整列表，而是要说明所有被称为方法的计算都必须考虑到计算复杂性。 – MrSmith42

看起来它会比O（n2）多。下面是程序代码与动态编程..不是java，但将作为算法有用 http://www.geeksforgeeks.org/longest-palindromic-substring-set-2/

来源

2017-05-29 11:26:17

计算字符串中最长的回文子字符串

回答

相关问题