1

このアルゴリズムの複雑さは? 少なくとも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"));
}
4

1 に答える 1

2

はい。の複雑さは O(n) であり、 からisCharPalindromen 回呼び出しているため、複雑さは O(n^2) ですlongestPrefixPalindrome。

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

それに応じて変更を加える方法を知っていると確信していますlongestPrefixPalindrome。

ただし、@ pajton の回答を見てください。考えてみれば、複雑さを O(n) まで下げることができます。私が与えた答えは、実際にそれができることについてのヒントを与えてくれます。

于 2011-04-09T21:53:48.537 に答える