JavaScript에서 주어진 단어 배열로 문자열을 분할할 수 있는지 확인하는 방법

문제 개요

빈 문자열이 아닌 하나의 문자열 str과, 공백 없이 이루어진 단어들로 구성된 문자열 배열 arr이 주어집니다. 이때 str을 배열에 존재하는 하나 이상의 단어를 공백으로 구분한 시퀀스 형태로 분할할 수 있는지 판별하는 함수를 작성해야 합니다.

참고 사항

• 분할 과정에서 배열에 있는 동일한 단어를 여러 번 재사용할 수 있습니다.
• 배열에는 중복된 단어가 포함되어 있지 않습니다.

예제 1

입력이 다음과 같다고 가정해 보겠습니다.

const str = "applepenapple";
const arr = ["apple", "pen"];

이 경우 출력값은 true입니다. 그 이유는 다음과 같습니다.

"applepenapple"은 "apple pen apple" 형태로 분할할 수 있습니다.

구현 코드

위 문제를 해결하는 전체 코드는 다음과 같습니다 −

const str = "applepenapple";
const arr = ["apple", "pen"];
const wordSequence = (str = '', arr = []) => {
    const map = {}
    function helper(str) {
       if (map.hasOwnProperty(str)) {
           return map[str]
       } else if (str=='') {
           return true
       }
       for (let i=0;i<=str.length;i++) {
           if (
              arr.includes(str.slice(i)) &&
              helper(str.slice(0, i))
           ){
              map[str] = true
              return true
           }
        };
        map[str] = false;
        return false;
    };
    return helper(str)
};
console.log(wordSequence(str, arr));

알고리즘 동작 원리

이 코드는 재귀 호출과 메모이제이션을 결합한 대표적인 동적 계획법(DP) 기반 풀이입니다. 각 단계의 동작은 다음과 같습니다.

• helper 함수는 문자열을 가능한 모든 위치에서 앞부분과 뒷부분으로 나누어 검사합니다.
• 뒷부분(str.slice(i))이 배열 arr에 포함된 단어라면, 남은 앞부분(str.slice(0, i))에 대해 재귀적으로 동일한 검사를 반복합니다.
• 한 번 계산한 결과는 map 객체에 캐싱해 두기 때문에, 동일한 부분 문자열에 대한 중복 연산을 피할 수 있어 실행 속도가 크게 향상됩니다.
• 재귀 호출 과정에서 문자열이 완전히 소진되어 빈 문자열이 되면, 모든 단어가 성공적으로 분할된 것으로 판단하고 true를 반환합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

true