最長のpalindrome接頭辞complextity

Question

このアルゴリズムの複雑さは何ですか？それは少なくともO（n^2）のようです。

// civic 
public static boolean isCharPalindrome(String test) { 
     String stripped = test.toLowerCase().replaceAll("[^0-9a-zA-Z]", ""); 
     for(int i = 0; i < stripped.length()/2; i++) { 
      if(stripped.charAt(i) != stripped.charAt(stripped.length() - 1 - i)) { 
       return false; 
      } 
     } 
     return true; 
    } 

// ILLINOISURB 
public static String longestPrefixPalindrome(String test){ 
    String max_prefix = test.substring(0,1); 
    for(int i=test.length()-1; i>=0; i--){ 
     String maxPrefix = test.substring(0, i); 
     if(isCharPalindrome(maxPrefix)){ 
      return maxPrefix; 
     } 
    } 

    return max_prefix; 
} 

public static void main(String[] args) { 
    String str = "A man, a plan, a canal, Panama!"; 
    System.out.println("isCharPalindrome:" + isCharPalindrome("A man, a plan, a canal, Panama!")); 
    System.out.println("longestPrefixPal:" + longestPrefixPalindrome("NILLINOISURB")); 
} 

Answer 1

はい。 isCharPalindromeの複雑さはO（n）であり、これをlongestPrefixPalindromeからn回呼び出すので、複雑さはO（n^2）です。

しかし、最も長いプレフィックスから始め、テストされたプレフィックスのサイズを小さくすることで、複雑さを軽減できます。これを行うと、あなたはpaliendromeを見つけるとすぐにメソッドを終了することができます。あなたは毎回最後まで行く必要はありません。

これに応じてlongestPrefixPalindromeに変更する方法を知っていることをお約束します。

@パジョンの答えを見てください。あなたがそれについて考えるなら、複雑さをO（n）まで得ることができます。私が与えた答えは実際にあなたにそれができることについてのヒントを与えるでしょう。