[leetCode] 28. Implement strStr() (Easy) 풀이

❓ 문제

Implement strStr().

strStr()을 구현합니다.

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

두 개의 문자열 needle과 haystack이 주어지면 haystack에서 needle이 처음 나타나는 색인을 반환하거나 needle이 haystack의 일부가 아닌 경우 -1을 반환합니다.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

'needle'이 빈 문자열이면 무엇을 반환해야 합니까? 이것은 인터뷰 중에 물어볼 수 있는 훌륭한 질문입니다.

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().

이 문제의 목적을 위해 바늘이 빈 문자열이면 0을 반환합니다. 이것은 C의 strstr() 및 Java의 indexOf()와 일치합니다.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

❗ 내 답변

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

indexOf()를 사용하면 한번에 문제가 해결됐다.
하지만 문제 의도가 이 indexOf 자체를 구현해보라는 듯 해서
아래 방법으로 다시 풀어보았다.

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    for (let i = 0; i < haystack.length; i++) {
        const compareStr = haystack.slice(i, i + needle.length);
        if (needle === compareStr)
            return i;
    }

    return -1;
};

haystack을 반복 돌면서 needle 길이만큼 잘라낸다.
그리고 잘라낸 문자열과 needle을 비교해 값이 같으면 i를 반환하게 했다.

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
// 0, 1
var strStr = function(haystack, needle) {
  for(let x = 0; x <= haystack.length - needle.length; x = x + 1) {
    for(let y = 0; y < needle.length; y = y + 1) {
      if(haystack[x + y] === needle[y]) {
        if(y === needle.length - 1) {
          return x;
        }
      } else {
        y = needle.length;
      }
    }
  }

  return -1;
};

for문을 두번 돌면서 needle의 길이만큼
haystack과 needle을 한문자씩 비교하면서 반환하고 있다.
따로 Javascript 내장함수를 쓰지 않아 결과가 빠르게 나온 것 같다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (!haystack.includes(needle)) return -1;
    if (needle.length === 0) return 0;
    const haystackArray = haystack.split(needle);
    return haystackArray[0].length;
};

haystack에서 needle로 split을 하고,
split된 배열의 첫번째 요소의 길이를 반환했다.
굉장히 직관적이고 신박한 것 같다. 이런 생각은 어떻게 하는거지..

💡 개선 방안

Javascript 내장 함수 사용을 줄여 속도를 더 빠르게 하자.