[leetcode] Find the Index of the First Occurrence in a String

28. 문자열에서 처음 발생하는 인덱스 찾기

두 문자열 haystack과 needle이 주어지면 haystack에서needle이 처음 발생한 인덱스를 반환하거나 needle이 haystack의 일부가 아닌 경우 -1을 반환합니다.

예 1:
입력: haystack = "sadbutsad", needle = "sad"
출력: 0
설명: "sad"는 인덱스 0과 6에서 발생합니다.
그 중 첫 번째는 인덱스 0에서 발생하므로 0을 반환합니다.

예 2:
입력: haystack = "leetcode", needle = "leeto"
출력: -1
설명: "leetcode"에서 "leeto"가 발생하지 않아 -1을 반환합니다.

문제 정리

1. 두개의 문자열 haystack, needle이 주어졌을때, needle이 haystack에서
   처음으로 발생하는 인덱스를 반환하는 문제이다. \*만약 needle이 haystack에 존재하지않으면 -1을 반환한다.

생각한 풀이방법

1. 먼저 needle이 빈 문자열인지 판별한다. 비어있으면 0을 반환한다.
2. haystack의 문자열을 반복문으로 돌면서 다음 단계들을 수행한다.
   a. 현재 인덱스에서 시작하는 haystack의 부분 문자열과 needle의 첫 번째 문자가 일치하는지 확인한다.
   b. 첫 번째 문자가 일치하면, found 변수에 true를 심어준다. 두번째 반복문으로 이어지는 문자들도 일치하는지 확인한다. 일치하지않은 문자열을 발견하면 found 변수를 false로 변경해준다.
   c. 모든 문자가 일치하면 현재 인덱스를 반환한다.
3. 모든 인덱스를 순회한 후에도 일치하는 부분 문자열을 찾지 못한 경우 -1을 반환한다.

 

 

작성코드🎈

function strStr(haystack, needle) {
//needle 문자열이 비어있을경우 0 리턴
  if(needle.length === 0) {
    return 0;
  }

  for(let i = 0; i <= haystack.length - needle.length; i++) { //i<=3 i가 3보다 같거나 작을때까지
    if(haystack[i] === needle[0]) { //일치하는 문자가 없으면 바로 return -1로 이동, 
    //일치하는 문자가 있으면 두번째 for문으로 이동
      let found = true; 

      for(let j = 1; j < needle.length; j++) {
      //needle의 두번째 문자열부터 마지막문자열까지 돌면서 판별
        if(haystack[i + j] !== needle[j]) {
          found = false;
          break;
        }
      }
 //found가 true면 문자열이 일치하는 것이므로 i를 리턴
      if(found) {
        return i;
      }
    }
  }
  return -1; //for문을 다 돌았는데도 일치하는 문자열이 없으면 -1을 리턴
}

let haystack = "leetcode",
    needle = "leeto";
    
 console.log(strStr(haystack, needle));

 

found 변수를 첫 번째 for 안에서 선언한 이유는? 

첫 번째 for문 내에서 haystack[i] === needle[0] 조건이 만족될 때, found 변수는 true로 설정되고,

두 번째  for문으로 들어간다. 두 번째 for문에서 needle의 나머지 문자들이 모두 일치하는지 확인하며,

일치하지 않는 경우 found를 false로 설정하고 두 번째 for문을 종료된다.

첫 번째 for문이 계속 진행되면서 다음 인덱스에서 found 변수는 다시 true로 초기화되고, 같은 과정을 반복된다.

이렇게해야 각 인덱스마다 일치하는 문자열을 정확하게 판단 할 수 있다.

 

첫 번째 반복문에서 haystack.length - needle.length로 범위설정을 지정한 이유?

일반적으로 문자열을 찾는 문제에서는 haystack.length - needle.length를 사용하여 반복문의 범위를 설정한다.

이렇게 설정하면 haystack에서 needle을 찾을 때 문자열 범위를 벗어나지 않도록 할 수 있기때문이다.

대부분의 경우, 문자열을 찾는 문제에서는 주어진 haystack 문자열에서 needle 문자열을 찾기 시작할 수 있는

최대 인덱스를 고려하여 범위를 설정해야 한다.

 

예를 들어, haystack 배열이 [1, 2, 3, 4, 5]이고 needle 배열이 [3, 4]인 경우를 살펴보자.

이 경우 반복문의 범위를 설정하기 위해 haystack.length - needle.length를 사용할 수 있다.

• haystack.length는 5 (haystack 배열 [1, 2, 3, 4, 5]의 길이)
• needle.length는 2 (needle 배열 [3, 4]의 길이)
• haystack.length - needle.length는 5 - 2 = 3

따라서, 반복문에서 i의 최대값은 3이 된다 .

이렇게 설정하면, 배열 범위를 벗어나지 않고 needle 배열을 찾을 수 있다.