Longest String Chain

Description

Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

 

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

 

Note:

1. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] only consists of English lowercase letters.

 

Solution(javascript)

/*
 * @lc app=leetcode id=1048 lang=javascript
 *
 * [1048] Longest String Chain
 */

// @lc code=start
// /** 1: Top-down Approach
//  * @param {string[]} words
//  * @return {number}
//  */
// const longestStrChain = function (words) {
//   words.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 memo = {}
//   const aux = (index) => {
//     if (memo[index] !== undefined) {
//       return memo[index]
//     }
//     let max = 0
//     for (let i = index + 1; i < words.length; i++) {
//       if (isPredecessor(words[index], words[i])) {
//         max = Math.max(
//           max,
//           1 + aux(i),
//         )
//       }
//     }
//     memo[index] = max
//     return memo[index]
//   }
//   let max = 0
//   for (let i = 0; i < words.length; i++) {
//     max = Math.max(max, 1 + aux(i))
//   }
//   return max
// }

/** 2: Bottom-up Approach
 * @param {string[]} words
 * @return {number}
 */
const longestStrChain = function (words) {
  words.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 memo = []
  let max = 0
  for (let i = words.length - 1; i >= 0; i--) {
    memo[i] = 1
    for (let j = words.length - 1; j > i; j--) {
      if (isPredecessor(words[i], words[j])) {
        memo[i] = Math.max(
          memo[i],
          1 + memo[j],
        )
      }
    }
    max = Math.max(max, memo[i])
  }
  return max
}
// @lc code=end