最も長い回廊の部分文字列

palindromeは、同じ前方と後方を読む文字の任意のセットです.例えば:'正午'はpalindrome、' loon 'ではありません.これらの文字列の両方とも、palindromic部分文字列' oo 'を含みます.

目的

Palindromeである文字列の中で最長の文字集合を検索します.

解決策

解決方法1

これを解決するためにいくつかの異なる方法がありますが、私は個人的に使用した2つに固執するつもりです.私の最初の考えは、すべての可能な部分文字列を取得し、彼らがpalindromesだったかどうかを確認することでした.ストリングがpalindromeであるならば、長さをチェックしてください.長さが現在の最長の長さより大きい場合、現在の文字列と同じ長さを設定します.
このソリューションは簡単ですが、確実に動作しますが、しかし、恐ろしい問題があります.大きな文字列ではとても遅いです.o(n ^ 2)ランタイムを持つすべての可能な部分文字列を取得するネストされたループを持っていて、o(n ^ 3)の完全ランタイムを与えるO(n)であるPalindromeであるかどうかを各文字列をチェックする必要があります.私はこの解決策を私の端末のノードを使ってテストしました、そして、それはうまく働きました、しかし、私が解決を提出するために行ったとき、それは制限時間を超えたので、それは失敗しました.ちょうどあなたが好奇心旺盛であるならば、私は以下のこの解決のコピーを示します、しかし、我々は次に、より速いオプションを見ています.

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    // check base case
    // examine every possible substring
    // if substring and length is longer than current longest, set to longest
    // return longest
    if (isPalindrome(s)) {
        return s;
    }

    let current = '';

    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            let ss = s.substring(i, j);
            if (isPalindrome(ss)) {
                if (ss.length > current.length) {
                    current = ss;
                }
            }
        }
    }
    return current;
};

function isPalindrome(s) {
    let reverse = s.split('').reverse().join('');
    if (s === reverse) {
        return true;
    } else {
        return false;
    }
}

ソリューション2

私はこの問題を解決するいくつかの異なる方法を研究しなければならなかった.私は、少なくとも畳み込まれるように見えたアルゴリズムを研究するのを選びました.私はいくつかの擬似コードを書いて、より良いアルゴリズムを理解するために手でいくつかの繰り返しを行った.
すべての可能な部分文字をチェックする必要はありません.代わりに、文字列を一度繰り返すことができます.各インデックスで、現在のインデックスの左と右の位置が等しいかどうかを確認します.それらが等しいなら、部分文字列はpalindromeです.我々は、部分文字列がもはやPalindromeでないまで、左と右のポインタをインクリメントして、decrementingし続けます.部分文字列がPalindromeでない場合、内部ループを終了し、文字列内の次のインデックス(外側ループ)に進みます.
以下はこのソリューションで使用されるコードの断片です.

var longestPalindrome = function (s) {
    let longest = '';

    // loop through string once
    for (let i = 0; i < s.length; i++) {
        // use two different starting positions to
        // account for even or odd strings
        checkLeftAndRight(i, i);
        checkLeftAndRight(i, i + 1);
    }

    function checkLeftAndRight(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            // subtract left from right and add one to get current
            // length of substring
            if (right - left + 1 > longest.length) {
                // set longest to current substring
                longest = s.slice(left, right + 1);
            }
            left--;
            right++;
        }
    }

    return longest;
};

結論

これはおもしろい問題でした.これらの解決策を実践し、分析する私の目標は、ある日、私がそれらを研究しなければならないことなく遭遇する多くの問題のために複数の解決策を考えることができる大きい十分なツールキットを持つことです.誰かを助けてくれることを望みます.