【LeetCode】No.28: Implement strStr()
28題目。strStr()関数の自力実装です。
strであるhaystackと、strであるneedleが所与で渡され、needleの文字列がhaystack中に含まれる場合にはhaystack中のneedleがはじまるインデックス番号をリターンせよというものです。尚、needleが含まれない場合には-1を返し、needleが空の場合を0を返す。これはCではstrstr()、JavaではindexOf()という関数で同じ機能のものが存在しているようですね。
結論から言えばサクセスは出来ましたが、満足のいくものは書けませんでした。
needleがhaystackの中にある時はneedleの頭文字のインデックス取得すればええねん！という安易な感じで進めていたところmississippiの例に対応できず。needleは含むが、needleの頭文字は別の場所にもあるよというパターン。needleがissipiで本来なら4を返すべきところ1がリターンでダメ。結局はfor文のところで.find()を使ってneedleの位置を取得して無理やりサクセスした形に。意味ないやん。
・・ということで回答をチェック。そしたら仮に自分のやり方でやるにはneedleの頭文字なんぞを比較するのではなくif文の中でhaystackの方の範囲を絞ったうえでneedleと合致する箇所のインデックスを返すような手法でやっていました(if haystack[start:start + len(needle)] == needleのような感じ)。確かにそりゃそうか。頭文字なんていくらでも合致する可能性ありますしね。自分の考えが足りてなかった。
他にももっと洗練されたコード例もありましたが、割愛。
それにしてもhaystackとneedleという言葉。前者は「干し草の山」で後者は「針」でなんのこっちゃと思い調べたら”a needle in a haystack”という慣用句から来ているんですね。日本語でいえば砂漠で針を探すとかそういうものに近いでしょうか。いつか会話で使うことはまあないんでしょうけど、しれてよかったw
Problems 達成度: 1.91%(28/1463)
