説明#
strStr()関数を実装します。
haystack 文字列と needle 文字列が与えられた場合、haystack 文字列の中で needle 文字列が最初に出現する位置（0 から開始）を見つけます。存在しない場合は、-1を返します。
例 1:
入力: haystack = "hello", needle = "ll"
出力: 2
例 2:
入力: haystack = "aaaaa", needle = "bba"
出力: -1
注意:
needle が空の文字列の場合、どのような値を返すべきですか？これは面接でよくある質問です。
この問題では、needle が空の文字列の場合、0 を返すべきです。これは C 言語の strstr() および Java の indexOf() の定義と一致します。
アプローチ#
- needle が空の場合、0 を返す
- haystack 文字列を走査し、現在の文字と needle の文字が同じかどうかを判定し、異なる場合は続けて走査する
- needle の文字と同じ場合、残りの文字が一致するかどうかを確認し、needle の走査が終了したら一致する位置を返し、haystack の走査が終了したら - 1 を返し、一致しない文字が見つかった場合は現在の一致を中断して次の最初の文字を探す
- haystack の走査が完了しても一致が完了しなかった場合、-1 を返す
int strStr(char * haystack, char * needle) {
if(strlen(needle) == 0)
return 0;
for(int i=0;haystack[i] != '\0';i++) {//文字列を走査
if(needle[0] == haystack[i]) {//最初の文字が一致するかどうかを検索
for(int j=0;;j++) {//残りの文字が一致するかどうかを検索
if(needle[j] == '\0')
return i;
if(haystack[i+j] == '\0')
return -1;
if(needle[j] != haystack[i+j]) //残りの文字が一致しない場合
break;//現在の一致を中断
}
continue;//次の最初の文字を検索
}
}
return -1;//最初の文字が一致しなかった場合
}
注意#
- 一致の条件判定の順序に厳密な要件があります。needle の一致が完了した場合に成功を返し、needle の一致が完了せずに haystack の走査が完了した場合に - 1 を返し、最後に一致の判定を行います。