Pattern Matching 알고리즘

문제

하나의 긴 문자열에 배열 안의 단어가 포함되어 있으면 true, 포함되어 있지 않으면 false를 반환하라. 이때 string match 메소드는 사용하지 않도록 한다.

checkString("abcdabce", ["abcd", "abce"]); // returns [true, true]
checkString("abcababcde", ["abc"]) // returns [true]
checkString("i am gonna be a frontend developer", ["i", "gonna", "backend"]); // returns [true, true, false]

나의 풀이

🙅🏻‍♀️ 나의 첫 번째 풀이

function checkString(largeStr, smallStr) {
  const length = largeStr.length;
  const arr = smallStr.map((str) => {
    for (let i = 0; i < length; i++) {
      if (largeStr[i] === str[0]) {
        for (let j = 0; j < str.length; j++) {
          if (largeStr[i + j] !== str[j]) return false;
        }
        return true;
      }
    }
  });
  return arr;
}

결론부터 말하자면 이 풀이는 틀렸다. 그리고 비효율적이다.

largeStr을 하나하나 탐색하며 smallStr의 요소의 0번째 인덱스와 일치하면 그 요소의 길이만큼 탐색을 시작해 단 하나라도 다르면 false를 반환하는 것이다. 여기서 문제는 largeStr에 반복되는 문자열이 있을 경우다. "abcdabce" 과 ["abcd", "abce"] 를 비교할 때 [true, false] 가 나온다. 그 이유는 smallStr의 요소의 0번째 인덱스가 largeStr의 일부와 일치하는 곳이 두 부분인데 지금의 로직대로라면 앞 부분과만 비교를 하기 때문이다.

그리고 비교를 할 때마다 largeStr의 처음부터 검색하고 인덱스를 1씩 옮기므로 비효율적이다. 만약에 smallStr의 요소와 largeStr이 일치하지 않더라도 끝까지 하나하나 탐색할 것이다.

🙆🏻‍♀️ 나의 두 번째 풀이

function checkString(largeStr, smallStr) {
  const length = largeStr.length;
  const arr = smallStr.map((str) => {
    let check = true;
    for (let i = 0; i < length; i++) {
      if (largeStr[i] === str[0]) {
        for (let j = 1; j < str.length; j++) {
          if (largeStr[i + j] !== str[j]) {
            check = false;
            break;
          }
          check = true;
        }
        if (check) return true;
      }
    }
    return check;
  });
  return arr;
}

break문, continue문

• break문을 쓸 때: 가장 가까운 while, do-while, for, 또는 switch문을 종료하고 다음 명령어로 넘어갑니다.
• continue를 사용하는 경우, 그것은 가장 안쪽의 while, do-while, for 문을 둘러싼 현재 반복을 종료하고, 다음 반복으로 루프의 실행을 계속합니다. break문과 달리, continue 문은 전체 루프의 실행을 종료하지 않습니다. while 루프에서 그것은 다시 조건으로 이동합니다. for 루프에서 그것은 증가 표현으로 이동합니다.

나의 첫 번째 풀이가 비효율적이라는 것은 알지만 최대한 풀이를 활용하고 싶어서 break 를 써보았다. 전처럼 검색하는 문자가 다를 때 바로 리턴하지 않고 check 변수에 false를 할당하며 두 번째 for 문을 빠져나간다. 그리고 리턴되지 않았으니 끝까지 탐색하게 만든다.