[LeetCode] 28_ImplementstrStr -JavaScript

문제 링크 : 28_ImplementstrStr string 문제

 

haystack과 needle이 주어졌을 때 

needle이 haystack에 있는지 확인하고 있으면 해당 idx를 없으면 -1을 return한다.

 

 

 

☁︎ 처음 풀이

var strStr = function (haystack, needle) {
  let needleLen = needle.length;

  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      if (haystack.substring(i, i + needleLen) === needle) return i;
    }
  }
}

 

haystack의 개수만큼 for문을 돌며

그 첫 글자가 같다면 needle의길이만틈의 문자를 잘라서 비교한다.

 

strStr( 'hello', 'll')이 주어졌을대 아래와 같은 순서로 탐색하게 된다.

1. he !== ll

2. el !== ll

3. ll !== ll

 

위의 풀이는 정답이지만 haystack의 길이가 엄청 길다면?  거기다 needle이 운이 안좋게 맨 뒤에 있다면?!! 

아주 비효율적인 알고리즘이 될 것이다. 그래.. 알고리즘을 운에 맡길 순 없다.🥲 

 

 

 

 

☁︎ 개선 풀이

var strStr = function (haystack, needle) {

  const charToInt = (char) => char.charCodeAt() - 'a'.charCodeAt();
  if (needle.length === 0) return 0;
  if (haystack.length < needle.length) return -1;

  const base = 26;
  let nHash = 0;
  let hHash = 0;

  for (let i = 0; i < needle.length; i++) {
    nHash = nHash * base + charToInt(needle[i]);
    hHash = hHash * base + charToInt(haystack[i]);
  }
  
  if (nHash === hHash) return 0;

  const highOrder = base ** needle.length;

  for (let j = 1; j < haystack.length - needle.length + 1; j++) {
    hHash =
      hHash * base -
      charToInt(haystack[j - 1]) * highOrder +
      charToInt(haystack[j + needle.length - 1]);
      
    if (nHash === hHash) return j;
  }
  return -1;
};

charToInt : 알파벳 -> 숫자

needle의 hash nHash(ll)와 needle길이만큼의 가장앞 hHash(he)를 구한다.

둘을 비교해  같다면 두 문자는 같다는 의미로 답은 idx =0

 

highOrder: 가장 큰 hash값 

다음 hHash는 (el)인데 기존 he  - h + l 를 진행해 hHash(el)를 구하고

이둘을 비교해 같은면 해당 idx를 return한다.

 

만약 다 돌았는데도 return값이 없다면 그건 일치하지 않으므로 -1 return

 

 

 

해당 풀이를 참고해 공부했는데, 처음에는 이해가 되지 않았지만 차근차근 생각하며 이해했다.

🥳 이번 풀이를 통해, 코드의 시간복잡도를 고민할 필요성을 느꼈다.