ความยาวของห่วงโซ่สตริงที่ยาวที่สุดใน JavaScript

ลูกโซ่คำ

สมมติว่า 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));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

4