문제
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2 Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1 Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
풀이
haystack에서 needle이 존재하는 첫번째 인덱스를 리턴하면 되는 문제이다.
needle의 첫번째 문자를 Haystack에서 찾는 순간, needle의 길이만큼 haystack을 substring하고 두 문자열을 비교 한다.
이렇게 보면 되게 간단한 문제인거 같은데, 아래와 같은 생각 때문에 조금 시간을 잡아먹었다.
needle의 첫문자를 haystack에서 만났을때 haystack을 substr한 다음 일치하지 않은 경우, 반복문을 더 진행해야 한다.
이럴때, haystack의 바로 다음 인덱스부터 다시 반복을 진행하면 너무 낭비가 많을것 같았다. 그래서 좀 더 최적화 할 순 없을까 생각을 해봤다.
haystack의 포인터 i와 needle의 포인터 j가 있을때 i와 j를 증가시키면서 두 문자열을 비교한다. 두개가 틀렸을때 i가 그 틀린 시점에서 다시 needle과 비교를 해도 되지 않을까? 라고 생각했다.
하지만 그렇게 할 경우 만약 haystack="aaac" needle="aac"인 경우에 문제가 된다. 처음 두 문자 'a' 'a'가 일치했지만 세번째 문자 'a' != 'c'에서 틀렸다.
이럴때 i를 haystack의 인덱스 2부터 다시 needle과 반복을 하게 되면 안된다. 왜냐면 틀렸을때 haystack[1]부터 다시 비교를 시작하면 haystack에 needle이 포함되어있기 때문이다.
이런 예외 케이스에 대한 생각 때문에 조금 길어졌다.
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (!needle.length) return 0;
for (let i = 0; i < haystack.length; i++) {
const char = haystack[i];
if (char === needle[0]) {
const subhay = haystack.substr(i, needle.length);
if (subhay === needle) return i;
}
}
return -1;
};결과
