самая длинная палиндромная префиксная полнота - PullRequest
Новая
       32

самая длинная палиндромная префиксная полнота

1 голос
/ 10 апреля 2011

В чем сложность этого алгоритма? Кажется, по крайней мере, 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 Ответ

2 голосов
/ 10 апреля 2011

Да. Сложность O (n ^ 2), поскольку сложность isCharPalindrome равна O (n), и вы называете ее n раз из longestPrefixPalindrome.

Но вы можете уменьшить сложность, начав с самого длинного префикса, а затем уменьшив размер тестируемого префикса. Если вы сделаете это, вы можете выйти из метода, как только обнаружите палиндром. Вам не нужно идти до конца каждый раз.

Я уверен, что вы знаете, как внести изменения в longestPrefixPalindrome соответственно.

Посмотрите на ответ @pajton. Если вы думаете об этом, вы можете уменьшить сложность до O (n). Ответ, который я дал, на самом деле подскажет, что можно сделать.

...