最长的回文前缀完整性

这个算法的复杂性是什么?它似乎至少是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"));
}
    
已邀请:
是。复杂度为O(n ^ 2),因为
isCharPalindrome
的复杂度为O(n),你从
longestPrefixPalindrome
调用它n次。 但是,您可以通过从最长前缀开始,然后减小测试前缀的大小来降低复杂性。如果你这样做,你可以在发现症状后立即退出该方法。你不需要每次都到最后。 我相信你知道如何相应地改变
longestPrefixPalindrome
。 看看@pajton的答案。如果你考虑一下,你可以将复杂性降低到O(n)。我给出的答案实际上会给你一个关于可以做到的提示。     

要回复问题请先登录注册