JavaScript에서 가장 긴 문자열 체인의 길이

단어 사슬

word1이 word2와 같게 만들기 위해 word1의 아무 곳에나 정확히 하나의 문자를 추가할 수 있는 경우에만 word1이 word2의 전신이라고 가정해 보겠습니다. 예를 들어, "abc"는 "abac"의 선행자입니다.

단어 체인은 k>=1인 단어 [word_1, word_2, ..., word_k]의 시퀀스입니다. 여기서 word_1은 word_2의 선행 항목이고, word_2는 word_3의 선행 항목입니다.

문제

첫 번째이자 유일한 인수로 문자열 배열 arr을 취하는 JavaScript 함수를 작성해야 합니다.

배열 arr의 각 문자열은 영어 소문자로 구성됩니다. 우리의 함수는 주어진 배열, arr에서 선택된 단어로 단어 체인의 가능한 가장 긴 길이를 반환해야 합니다.

예를 들어, 함수에 대한 입력이 -

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

그러면 출력은 다음과 같아야 합니다. -

const output = 4;

출력 설명:

가장 긴 단어 체인 중 하나는 "a","ba","bda","bdca"입니다.

예시

이에 대한 코드는 -

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));

출력

콘솔의 출력은 -

4