java - 最长回文前缀复杂度

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

是的。复杂度为 O(n^2)，因为 isCharPalindrome 的复杂度为 O(n)，并且您从 longestPrefixPalindrome 调用它 n 次。

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

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

看看@pajton 的回答。如果你仔细想想，你可以将复杂度降低到 O(n)。我给出的答案实际上会提示您可以做到这一点。