JavaScript로 문자열이 배열 요소들의 조합인지 확인하는 방법

첫 번째 인수로 문자열 배열을, 두 번째 인수로 하나의 문자열을 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 두 번째 인수로 전달된 문자열이 배열에 포함된 문자열들을 어떤 순서로든 조합하여 만들어질 수 있는지 판별해야 합니다.

예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = ["for","car","keys","forth"];

그리고 검사할 문자열은 다음과 같습니다.

const str = "forthcarkeys";

이 경우 출력값은 true가 되어야 합니다. 해당 문자열은 배열의 3번, 1번, 2번 인덱스에 있는 요소들을 이어 붙인 것과 정확히 일치하기 때문입니다.

예제 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = ["for","car","keys","forth"];
const str = "forthcarkeys";
const checkPossibility = (str = '', arr = []) => {
   let possibilities = arr.reduce(function (r, a) {
      let p = str.indexOf(a);
      while (p !== -1) {
         r.push({ word: a, position: p });
         p = str.indexOf(a, p + 1);
      }
      return r;
   }, []);
   const findRecursively = (i, t) => {
      let s = t.slice(), j;
      if (i === possibilities.length) {
         return !t.join('');
      }
      if (possibilities[i].word.split('').every(function (c, j) {
         return s[j + possibilities[i].position] !== ''; })) {
         for (j = 0; j < possibilities[i].word.length; j++) {
            s[j + possibilities[i].position] = '';
         }
      }
      return findRecursively(i + 1, s) || findRecursively(i + 1, t);
   };
   return findRecursively(0, str.split(''));
};
console.log(checkPossibility(str, arr));

출력 결과

콘솔에 표시되는 출력은 다음과 같습니다.

true

코드 작동 원리

이 알고리즘은 크게 두 단계로 동작합니다.

1단계 – 등장 위치 탐색: reduce와 indexOf를 활용해 배열의 각 단어가 대상 문자열 안에서 등장하는 모든 위치를 찾아 { word, position } 형태의 객체로 possibilities 배열에 저장합니다.

2단계 – 재귀적 조합 탐색: findRecursively 함수는 각 후보 단어에 대해 '해당 위치에 배치하는 경우(s)'와 '배치하지 않는 경우(t)'라는 두 가지 분기를 모두 재귀적으로 탐색합니다. 단어를 배치할 때는 every 검사를 통해 이미 다른 단어가 차지한 자리(''로 표시됨)와 겹치지 않는지 확인한 뒤, 사용된 글자들을 빈 문자열로 치환합니다. 모든 후보를 검토한 시점에 남은 글자가 없어 t.join('')이 빈 문자열이 되면 true를 반환하고, 그렇지 않으면 false를 반환합니다.