[LeetCode]Implement strStr() (JS)

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

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

입출력 예
Input: haystack = "hello", needle = "ll"
Output: 2

접근

indexOf문제이다. 실제로 return haystack.indexOf(needle)을 하면 바로 통과한다.
그러나 indexOf가 어떻게 굴러가는지 작성하는 코드이므로 기능을 작성 해줘야 한다.

문제에서 요구한 사항들을 생각하면서 풀이 방법을 생각한다.

1. needle의 길이가 0이라면 0리턴
2. haystack에 needle이 존재하는지 검사하는 함수를 작성하는 것 이므로 haystack을 반복문으로 돌리면서 needle의 첫글자가 존재하면 다음글자역시 needle과 일치하는지 확인하는 작업을 반복한다.
3. 일치하면 그 인덱스를 바로 리턴
4. 반복문이 끝나고 나서 존재하지 않는다면 -1 리턴

코드

var strStr = function(haystack, needle) {
  
  if(!needle.length) return 0;
  let resultIndex = -1;
    
  for(let i = 0; i < haystack.length; i++){    
    if(haystack[i] === needle[0]){      
      let flag = true;
      let j = 0
      while(j < needle.length){   
        if(haystack[i + j] !== needle[j]){            
          flag = false;          
          break;       
        }         
        j++;          
      }     
      if(flag) return i;  
    }
  }
  return -1; 
};

나는 이 문제를 풀이하면서 boolean을 저장하는 변수 flag를 사용하였다. 그러나 굳이 선언하지 않더라도 while을 아래와 같이 고치면 가능하다...

while(j < needle.length){
  if(haystack[i + j] !== needle[j]){
    break;                
  }else if(j === needle.length - 1){                  
    return i;                
  }              
  j++;               
}

또 반복문을 한번 더 돌릴 필요없이 substring을 이용하면,

var strStr = function(haystack, needle) {
    if(!needle.length) return 0;
    let resultIndex = -1;
    
    for(let i = 0; i < haystack.length; i++){
        if(haystack[i] === needle[0]){
            let temp = haystack.substring(i, i + needle.length)
            if(temp === needle){
                return i;
            }
        }
    }
    return -1; 
};

런타임이 줄어들었다!