[leetcode]問題解答と解説。5. Longest Palindromic Substring [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
【5. Longest Palindromic Substring】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

[leetcode] 5. Longest Palindromic Substring ルール

exampleは実際の問題ページを見てください

[leetcode] 5. Longest Palindromic Substring 問題ページ

longest-palindromic-substring

[leetcode] 5. Longest Palindromic Substring

my code is not good(time out)

function longestPalindrome(s: string): string {
    let first = 0;
    let last = s.length;
    let palind = []
    let result = ""

    while(first < last || first !== last){
        if(s[first] === s[last]){
            palind.splice(first, 0, s[first])
            palind.splice(last, 0, s[last--])
            first++
            last--
            result = palind.join("")
            continue;
        }
        if(s[first + 1] === s[last]){
            palind.splice(first+1, 0, s[first])
            palind.splice(last, 0, s[last])
            result = palind.join("")
            first = first + 2
            last--
            continue;
        }
        if(s[first] === s[last - 1]){
            palind.splice(first, 0, s[first])
            palind.splice(last -1, 0, s[last])
            last = last -2
            first++

            result = palind.join("")
            continue;
        }

    }
    return result
}

longestPalindrome("babad")

何やっているのか分からなくなってきてタイムアウト

[leetcode] 5. Longest Palindromic Substring。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない

JavaScriptでfilterされている、discussはこちらから

これはyoutubeの解説見てやった。
これはC言語だが、JSに置き換えた
https://www.youtube.com/watch?v=fxwvVnBMN6I&t=874s

そっちの方が理解が進んだ。
Number型にしているのはTypeScriptで怒られたからで、JavaScriptならそれは不要

     let n = s.length
    let ans = "";
    let maxlength = 0;
    let dp = Array.from({length: n}).map(_ => Array.from({length: n}).fill(0)) // n分のマスを0埋めで作る
    for(let diff = 0; diff < n; diff++){
        for(let i = 0, j = i + diff; j< n ; i++, j++){
            // iはstart, jはスタート位置からいくつ離れているかになる
            if(i == j){ // 一緒の場合は必ずPalindromicになる// "abc"なら"a"、"b"、"c"にあたる
                dp[i][j] = 1;
            }
            else if (diff === 1){ // 次の文字が同じかどうか ex: "abc"なら"a"と"b"をチェックしている
                dp[i][j] = (s[i] === s[j]) ? 2 : 0 
            }
            else {
                 // スタート位置から2つ以上離れている場合
                 // "abc"なら"a"と"c"
                if(s[i] === s[j] && dp[i+1][j-1]){ // 間の"b"をチェック
                    dp[i][j] = Number(dp[i+1][j-1]) + Number(2); // 間にある文字数と両端の2文字分を追加
                }
            }
            // 毎回チェック
            if(dp[i][j]){
                if(j-i+1 > maxlength){ // j-i+1は文字数
                    maxlength = j-i+1;
                    ans = s.substr(i, maxlength) // 抽出
                }
            }
        }
    }
    return ans

[leetcode] 5. Longest Palindromic Substringをやってみて感想

• dpが面白くなってきた。これは学んでないと思い付かない

カテゴリー leetCode