[leetcode] 問題解答と解説。28. Implement strStr() [easy]

年末まで毎日leetcodeと向き合います。

今日のLeatCodeはこちら。

文字列2つ与えるので一方の文字列の中に他方の文字列が含まれているその最初のindexを得よというもの

Implement strStr 問題

Implement strStr() [easy]

感想

この解決方法もいいと思ったが、
https://leetcode.com/problems/implement-strstr/discuss/116860/JavaScript-Solution-Beats-100

substring自体がO(n)だ!みたいなコメントがあって、
厳しいなと思いつつ、避けた

https://leetcode.com/problems/implement-strstr/discuss/590911/JavaScript-solution.-No-built-in-methods.

O(n2)かと思ったがそうでもないっぽい
最初の文字を見つけ次第loopが始まる

これは負けたので理解に努める

Implement strStr() 回答一例

    if(needle === "" || needle === haystack) return 0 // 空文字ならfalse
    if(haystack.length < needle.length) return -1 // needleが多い場合含まれないので見つからない-1

    for(let i = 0; i < haystack.length - needle.length + 1; i++){ // 検索する文字の開始位置から回すため
        if(haystack[i] === needle[0]){ // 最初の文字として見つかったら開始
            for (let j = 0; j < needle.length; j++) {
                if(haystack[i + j] !== needle[j]){ // haystackをjの分だけ移動していってマッチしなかったらbreak
                        break;
                } else if(j === needle.length-1){ // jがneedlesの文字数に達したら会っていたことになる
                    return i
                }
            }
        }
    }
    return -1

カテゴリー leetCode