1048. Longest String Chain

Standard

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"`.

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.

Java Solution

``````class Solution {
public int longestStrChain(String[] words) {
HashMap<String, Integer> longestPre = new HashMap<>(); // Including the word itself
TreeMap<Integer, List<String>> wordsByCharLength = new TreeMap<>();
int res = 1;
for (String word : words) {
wordsByCharLength.putIfAbsent(word.length(), new LinkedList<>());
wordsByCharLength.get(word.length()).add(word);
}
int longest = wordsByCharLength.lastKey();
for (int i = 1; i <= longest; i++) {
if (!wordsByCharLength.containsKey(i)) {
continue;
}
for (String curWord : wordsByCharLength.get(i)) {
if (!wordsByCharLength.containsKey(i - 1)) {
longestPre.put(curWord, 1);
continue;
}
int prevLongest = 0;
for (String prevWord : wordsByCharLength.get(i - 1)) {
if (isPredecessorOf(prevWord, curWord)) {
prevLongest = Math.max(prevLongest, longestPre.get(prevWord));
}
}
longestPre.put(curWord, prevLongest + 1);
res = Math.max(res, prevLongest + 1);
}
}
return res;
}

private boolean isPredecessorOf(String prevWord, String curWord) {
int skipped = 0;
int i = 0;
while (i < prevWord.length() && i + skipped < curWord.length()) {
if (prevWord.charAt(i) != curWord.charAt(i + skipped)) {
if (skipped == 0) {
skipped = 1;
continue;
} else {
return false;
}
}
i++;
}
return true;
}
}``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.