1048. Longest String Chain

Problem

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain** **is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a *predecessor* of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

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

  Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3:

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

  Constraints:

• 1 <= words.length <= 1000

• 1 <= words[i].length <= 16

• words[i] only consists of lowercase English letters.

Solution

/**
 * @param {string[]} words
 * @return {number}
 */
var longestStrChain = function(words) {
    var map = Array(17).fill(0).map(() => []);
    for (var i = 0; i < words.length; i++) {
      map[words[i].length].push(words[i]);
    }
    var max = 0;
    for (var i = 0; i < words.length; i++) {
      max = Math.max(max, helper(map, words[i], {}));
    }
    return max;
};

var helper = function(map, word, dp) {
  if (dp[word] !== undefined) return dp[word];
  var arr = map[word.length + 1] || [];
  var max = 1;
  for (var j = 0; j < arr.length; j++) {
    if (!isPredecessor(word, arr[j])) continue;
    max = Math.max(max, 1 + helper(map, arr[j], dp));
  }
  dp[word] = max;
  return max;
};

var isPredecessor = function(word1, word2) {
  var i = 0;
  var skipped = false;
  for (var j = 0; j < word2.length; j++) {
    if (word1[i] !== word2[j]) {
      if (!skipped) {
        skipped = true;
        continue;
      } else {
        return false;
      }
    }
    i++;
  }
  return true;
};

Explain:

DFS and DP.

Complexity:

• Time complexity : O(n ^ 2).
• Space complexity : O(n).