最長回文文字列

原文リンク:Longest Palindromic Substring
最長回文文字列を見つけるのは古典的な符号化面接問題であり,この問題に対する3つの異なる解決策をまとめた.

ダイナミックプログラムはsを入力文字列にし、iとjは文字列の2つのインデックスである.2 D配列「table」を定義し、table[i][j]にiからjまでのサブ文字列が返信文であるかどうかを示す.

条件を変更:

table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
=>
table[i][j] == 1

時間O(n^2)空間O(n^2)

public String longestPalindrome(String s) {
    if(s==null || s.length()<=1)
        return s;
 
    int len = s.length();
    int maxLen = 1;
    boolean [][] dp = new boolean[len][len];
 
    String longest = null;
    for(int l=0; lmaxLen){
                   maxLen = j-i+1; 
                   longest = s.substring(i, j+1);
                }
            }
        }
    }
 
    return longest;
}

たとえば、入力文字列が「dabcba」の場合、最終的な行列は次のようになります.

1 0 0 0 0 0 
0 1 0 0 0 1 
0 0 1 0 1 0 
0 0 0 1 0 0 
0 0 0 0 1 0 
0 0 0 0 0 1 

表から最も長い文字列がtableであることが明らかになった[1][5].

簡単なアルゴリズム時間O(n^2),空間O(1)

public String longestPalindrome(String s) {
    if (s.isEmpty()) {
        return null;
    }
 
    if (s.length() == 1) {
        return s;
    }
 
    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i++) {
        // get longest palindrome with center of i
        String tmp = helper(s, i, i);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }
 
        // get longest palindrome with center of i, i+1
        tmp = helper(s, i, i + 1);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }
    }
 
    return longest;
}
 
// Given a center, either one letter or two letter, 
// Find longest palindrome
public String helper(String s, int begin, int end) {
    while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
        begin--;
        end++;
    }
    return s.substring(begin + 1, end);
}

マンチェルアルゴリズムはO(n)時間の複雑さの利点をもたらすが,マンチェルアルゴリズムの計算はずっと複雑である.典型的ではないので、時間を無駄にする必要はありません.