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^2)，因为 的复杂度isCharPalindrome为 O(n) 并且您从 . 调用它 n 次longestPrefixPalindrome。

但是您可以通过从最长的前缀开始然后减小测试的前缀的大小来降低复杂性。如果这样做，您可以在找到回文后立即退出该方法。你不需要每次都走到最后。

我相信您知道如何进行相应的更改longestPrefixPalindrome。

不过看看@pajton 的回答。如果您考虑一下，您可以将复杂度降低到 O(n)。我给出的答案实际上会给你一个关于可以做到的提示。

于 2011-04-09T21:53:48.537 回答