หาความยาวโซ่คำที่ยาวที่สุดใน JavaScript

โซ่คำ (Word Chain)

เราจะเรียกว่า word1 เป็น predecessor ของ word2 ก็ต่อเมื่อเราสามารถเพิ่มตัวอักษรเพียงตัวเดียวที่ตำแหน่งไหนก็ได้ใน word1 เพื่อให้เท่ากับ word2 ตัวอย่างเช่น "abc" เป็น predecessor ของ "abac"

โซ่คำคือลำดับของคำ [word_1, word_2, ..., word_k] โดยที่ k >= 1 และ word_1 เป็น predecessor ของ word_2, word_2 ของ word_3, และต่อไป

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของสตริง 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