java - 文字を削除して、既存の文字列から回文を作成します

Question

0個以上の文字を削除して、単語から取得できる最長の回文の長さを決定するにはどうすればよいですか。

例：amanQQQapl12345anacaZZZnalpaXXXna67890ma
最長の回文は21桁になります。

Answer 1

これは、動的計画法によって解決できます。d [i、j]を、元の文字列の最長の回文の長さとして定義します。

s [i] = s [j]、d [i、j] = max（d [i + 1、j-1] + 2、d [i、j-1]、d [i + 1、j]の場合）。

それ以外の場合、d [i、j] = max（d [i、j-1]、d [i + 1、j]）。

Answer 2

Wという単語の中で最も長い回文は、Wとそのミラーの最長共通部分列です。

O（n²）時間とO（n）空間で計算できます。ここで、nはWの長さですが、回文を作成するために数文字を削除するだけでよいことがわかっている場合は、より複雑にすることができます。

Answer 3

パリドロームは、最大で1つの奇数のカウントされた文字、つまり中央の文字と、任意の数の偶数のカウントされた文字を持つことができます。

あなたは各文字の頻度を数えることができます。各文字にすべてまたはまったくない場合は、各文字にカウント/ 2 * 2を追加し、いずれかの文字のカウントが奇数の場合は1を追加します。

Answer 4

これは、@ Ramboによる回答の適切な実装であり、他の人が彼の回答があまりにも簡潔であると判断した場合に備えてです。以前の結果のキャッシュを追加しましたが、個別のシンボルの最大数が最大1000であるという条件の下で。これにより、同じサブブランチを使用する複数のブランチにより、大幅な高速化が実現します。

int d[1000][1000] = {0}; // To store result of previous computation

int computeMaxPalindromeLength(vector<int>& a, int start, int end) {
    if(d[start][end] != 0) // If not precomputed, recompute.
        return d[start][end];
    if(start == end) { // The mid character should be taken as 
        d[start][end] = 1;
        return 1;
    }
    else if(start == end-1) {
        d[start][end] = (a[start] == a[end])?2:1;
        return d[start][end];
    }
    if(a[start] == a[end]) {
        d[start][end] = max( 2 + computeMaxPalindromeLength(a, start+1, end-1), 
            max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1)));
    } else {
        d[start][end] = max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1));
    }
    return d[start][end];
}

上記のメソッドを次のように呼び出します：-

vector<int>& a; // Convert each character of string to digit if working with alphanumeric characters.
int maxPalindromeLength = computeMaxPalindromeLength(a, 0, a.size()-1);