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