[LeetCode] Implement strStr()

🧑‍💻 언어 및 제출 결과

• 사용 언어: JavaScript
• 통과 여부: ✅

🧠 풀이 설명

첫 번째 풀이

indexOf만 쓰면 되는거라 생각은 했지만 그럼 재미 없을 거 같아서 다른 풀이들을 풀었습니다.

const strStr_indexOf = (haystack, needle) => haystack.indexOf(needle);

---

두 번째 풀이

const strStr = (haystack, needle) => {
  for (let i = 0; i <= haystack.length - needle.length; i++) {
    const sliceStr = haystack.slice(i, i + needle.length);

    if (sliceStr === needle) return i;
  }
  return -1;
};

1. 반복을 haystack.length - needle.length만큼만 한 이유를 예를 들어 설명하자면, 첫 번째 인자 length가 5, 두 번째 인자 length 3일 경우 탐색 하는 인덱스는 0 ~ 2, 1 ~ 3, 2 ~ 4, 입니다. 그러므로 탐색할 글자(두 번째 인자)의 length를 탐색 당할 글자(첫 번째 인자)에 - 하면 남는 값 없이 탐색 됩니다. 결론적으로 0 ~ 2까지만 반복문을 돌리면 되기 때문에 5 - 3 === haystack.length - needle.length로 반복 횟수를 정했습니다. 만약 haystack.length만큼만 반복할 경우 haystack의 마지막 값부터 ~ needle.length까지는 남는 값들까지 처리되어 사이드 이펙트가 발생할 것 입니당.

for (let i = 0; i <= haystack.length - needle.length; i++)

2. 비교할 str을 만들려면 위에서 말한 것처럼 0 ~ 2, 1 ~ 3... 대로 잘랐습니다
   • 마이너하지만 slice 할 때 자주 헷갈리는 것 첫 번째 인자로 넘어온 시작 인덱스가 가리키는 값은 포함하지만, 두 번째 인자로 넘어온 종료 인덱스가 가리키는 값은 포함하지 않음 (그냥 start는 index, end는 length라고 생각하면 편하다) slice(start(index),end(length),...)
3. const sliceStr = haystack.slice(i, i + needle.length);
4. 자른 거랑 needle이랑 비교하면 끗
5. if (sliceStr === needle) return i;

---

세 번째 풀이

const strStr_recursive = (haystack, needle, i = 0) => (
  (sliceStr = haystack.slice(i, i + needle.length)),
  (valid = i <= haystack.length - needle.length),
  !valid ? -1 : sliceStr === needle ? i : strStr_recursive(haystack, needle, i + 1)
);

의미는 없지만 재귀로 풀 수 있을 거 같아서 해 봤습니다.
코드 자체는 더 짧지만 가독성이 떨어지고 성능 차이 있어요ㅜ

1. 콤마 연산자를 사용해 변수를 할당해줍니다.(2번 풀이와 동일합니다.)
2. (sliceStr = haystack.slice(i, i + needle.length))

(콤마 연산자는 왼쪽부터 실행하고 마지막 표현식의 값을 반환)

2. 유효성 검사를 위한 valid 변수를 써줍니다. (없어도 되지만 가독성을 위함입니다,, 허허)
3. (valid = i <= haystack.length - needle.length)

• 현재 인덱스가 탐색 가능한 범위 내에 있는지 확인하는 역할을 합니다.
• i가 haystack.length - needle.length를 넘으면 needle 길이만큼 자를 수 없습니다 (2번 풀이 사용한 반복 조건과 동일합니다.)

3. 삼항 연산자로 조건을 분기처리 해줍니다.
4. !valid ? -1 : ...

• valid가 false면(범위 벗어남) -1 반환 => 못 찾았다는 의미

sliceStr === needle ? i : ...

• 잘라낸 문자열이 needle과 같으면 현재 인덱스 i 반환 => 찾았다는 의미

strStr_recursive(haystack, needle, i + 1)

• 둘 다 아니면 다음 위치(i+1)로 재귀 호출

4. 동작 예시
5. strStr_recursive("hello", "ll", 0) → sliceStr = "he", valid = true, "he" !== "ll" → 재귀(i=1) → sliceStr = "el", valid = true, "el" !== "ll" → 재귀(i=2) → sliceStr = "ll", valid = true, "ll" === "ll" → return 2

// 번외 극한의 한줄
const strStr_recursive2 = (h, n, i = 0) => i > h.length - n.length ? -1 : h.slice(i, i + n.length) === n ? i : strStr_recursive2(h, n, i + 1);

📊 시간/공간 복잡도

n = haystack의 길이

m = needle의 길이

✅ 어떠한 근거로 시간/공간 복잡도가 이렇게 나왔는지 설명해주세요.

첫 번째 풀이

• 시간 복잡도: O(n × m)
  • 최악의 경우 모든 위치에서 needle 전체를 비교
• 공간 복잡도: O(1)
  • 추가 메모리 X

두 번째 풀이

• 시간 복잡도: O(n × m)
  • 반복문: O(n)번 실행
  • slice: 매번 O(m) 시간 (m개 문자 복사)
  • 문자열 비교: O(m) 시간
• 공간 복잡도: O(m)
  • slice가 매번 새 문자열 생성 (길이 m)

세 번째 풀이

• 시간 복잡도: O(n × m)
  • 재귀 호출: 최대 O(n)번
  • 각 호출마다 slice와 비교: O(m)
• 공간 복잡도: O(n + m)
  • 재귀 콜 스택: O(n) (스택 오버플로우 위험 있음)
  • slice로 생성되는 문자열: O(m)

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.

첫 번째 풀이

두 번째 풀이

세 번째 풀이