건초 더미와 바늘의 두 문자열이 주어졌을 때, 건초 더미 문자열에서 바늘 문자열의 첫 번째 일치하는 부분의 첨자를 구합니다. 바늘이 건초 더미에 포함되지 않으면 -1을 반환합니다.
예 1:
입력: 건초더미= "sadbutsad", needle = "sad"
출력: 0
설명: "슬픈"은 아래 첨자 0과 6에서 일치합니다.
첫 번째 일치의 첨자는 0이므로 0을 반환합니다.
예 2:
입력: 건초더미= "leetcode", needle = "leeto"
출력: -1
설명: "leeto"는 "leetcode"에 나타나지 않으므로 -1이 반환됩니다.
팁:
1 <= haystack.length, needle.length <= 401- 건초더미와 바늘은 영문 소문자로만 구성됩니다.
문제 해결 아이디어:
원본 건초 더미의 각 문자를 '원점'으로 반복하고 매번 원본 문자열의 '원점'과 일치하는 문자열의 '첫 번째'에서 일치하도록 시도합니다:
일치 성공: 이 일치의 시작점을 반환합니다. 실패: 원본 문자열의 다음 '시작점'을 열거하고 일치를 다시 시도합니다.
public class Problem_0028_ImplementStrStr {
public int strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
char[] s = haystack.toCharArray();
char[] p = needle.toCharArray();
for (int i = 0; i < n - m; i++) {
// 원본 문자열의 '원점'과 일치하는 문자열의 '첫 번째'부터 시작하여 일치를 시도합니다.
int a = i;
int b = 0;
while (b < m && s[i] == p[b]) {
a++;
b++;
}
// 일치가 완료되면 원본 문자열의 '원점' 접미사를 반환합니다.
if (b == m) return i;
}
return -1;
}
}
