JavaScript로 구하는 가장 긴 문자열 체인(Longest String Chain)의 길이

단어 체인(Word Chain)이란?

word1에 정확히 한 글자를 임의의 위치에 추가했을 때 word2와 완전히 같아지는 경우, word1을 word2의 선행자(predecessor)라고 합니다. 예를 들어 "abc"는 "abac"의 선행자입니다.

단어 체인(word chain)은 [word_1, word_2, ..., word_k](k >= 1) 형태의 단어 시퀀스로, word_1은 word_2의 선행자이고, word_2는 word_3의 선행자인 식으로 앞뒤 단어가 선행자 관계로 연결된 것을 의미합니다.

문제 정의

문자열 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 배열의 각 문자열은 영어 소문자로만 구성되어 있으며, 함수는 주어진 배열에서 단어들을 골라 만들 수 있는 가장 긴 단어 체인의 길이를 반환해야 합니다.

예를 들어 함수의 입력이 다음과 같다면 −

const arr = ["a","b","ba","bca","bda","bdca"];

출력은 다음과 같아야 합니다 −

const output = 4;

출력 설명

가장 긴 단어 체인 중 하나는 "a" → "ba" → "bda" → "bdca"입니다. 각 단어는 바로 앞 단어에 글자를 하나씩 추가해 만들 수 있으므로 체인의 길이는 4가 됩니다.

접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.

먼저 단어들을 길이 오름차순으로 정렬합니다. 그런 다음 뒤에서부터 각 단어를 기준으로, 자신보다 뒤에 있는(즉 더 길거나 같은 위치의) 단어 중 자신의 선행자 관계에 해당하는 단어를 찾아 체인 길이를 갱신합니다. 배열 array[i]에는 i번째 단어에서 시작하는 가장 긴 체인의 길이가 저장됩니다.

두 단어가 선행자 관계인지 확인하는 isPredecessor 함수는 두 단어의 길이 차이가 정확히 1인지 먼저 검사하고, word2에서 글자를 하나씩 제거해 보면서 word1과 일치하는지 확인합니다.

예제 코드

const arr = ["a","b","ba","bca","bda","bdca"];
const longestStrChain = (arr) => {
   arr.sort((a, b) => a.length - b.length);
   const isPredecessor = (word1 = '', word2 = '') => {
      if(Math.abs(word1.length - word2.length) !== 1){
         return false;
      };
      for(let i = 0; i < word2.length; i++){
         const word = word2.slice(0, i) + word2.slice(i + 1);
         if(word === word1){
            return true;
         };
      };
      return false;
   };
   const array = [];
   let max = 0;
   for(let i = arr.length - 1; i >= 0; i--){
      array[i] = 1;
      for(let j = arr.length - 1; j > i; j--){
         if(isPredecessor(arr[i], arr[j])){
            array[i] = Math.max(
               array[i],
               1 + array[j],
            );
         };
      };
      max = Math.max(max, array[i]);
   };
   return max;
};
console.log(longestStrChain(arr));

출력 결과

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