Độ dài chuỗi từ dài nhất trong JavaScript

Chuỗi từ (Word Chain)

word1 là tiền tố của word2 nếu và chỉ nếu ta có thể thêm đúng một chữ cái bất kỳ vị trí vào word1 để được word2. Ví dụ: "abc" là tiền tố của "abac".

Chuỗi từ là dãy [word_1, word_2, ..., word_k] với k ≥ 1, trong đó word_1 là tiền tố của word_2, word_2 của word_3, v.v.

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng chuỗi arr làm đối số duy nhất. Mỗi chuỗi chỉ chứa chữ cái thường. Hàm trả về độ dài lớn nhất có thể của chuỗi từ với các từ chọn từ mảng cho trước.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

const output = 4;

Giải thích đầu ra

Một trong các chuỗi từ dài nhất: "a","ba","bda","bdca".

Ví dụ minh họa

Mã thực hiện (DP + sắp xếp theo độ dài):

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

Đầu ra

Kết quả trong console sẽ là:

4