LeetCode 解答 #28. Implement strStr() プログラミング練習
問題:
難易度: easy
入力: 文字列haystackと文字列needle
目的: haystackの中でneedleと一致する文字列が存在する場合一致する最初のインデックスを返せ。存在しない場合は-1を返せ
出力: integer
入力された文字列haystackの中にneedleの文字列がsubstringとして存在しているか判断する問題。
すべてsubstringで試すのもいいが処理時間が長いのでアウト
注意すべき事:
- needleが空文字列だった場合0を返す
以下回答です。
class Solution { public int strStr(String haystack, String needle) { int len = haystack.length(); int needlelen = needle.length(); if (needlelen == 0) { return 0; } if (len == 0 || needlelen > len) { return -1; } for (int i=0; i< len; i++) { if (haystack.charAt(i) == needle.charAt(0)) { int j = 1; for (; j< needlelen; j++) { if (i+j > len-1) { break; } if (haystack.charAt(i+j) != needle.charAt(j)) { break; } } if (j == needlelen) { return i; } } } return -1; } }
haystackのエレメントを一つずつ見ていき、
needleの最初のエレメントと同じものがあった時
iでそのインデックスを記録。
jで再度for文を始め残りの文字列が一致しているかを確認。
すべて当てはまっていなければ-1を返します。
今日は以上。
よいプログラミング生活を!