JavaScript 中最长字符串链的长度

Z时代
2024-01-10
分类：综合

文字链

假设 word1 是 word2 的前身，当且仅当我们可以在 word1 的任意位置添加一个字母，使其等于 word2。例如，“abc”是“abac”的前身。

一个词链是一个词序列 [word_1, word_2, ..., word_k] 其中 k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。

问题

我们需要编写一个 JavaScript 函数，它接受字符串数组 arr 作为第一个也是唯一的参数。

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