1048. Longest String Chain

⭐⭐⭐

題目敘述

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.

解題思路

Solution

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestStrChain(String[] words) {
        int ans = 0;
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> map = new HashMap<>();

        for(String word : words){
            map.put(word, 1);
            for(int i = 0; i < word.length(); i++){
                String prev = word.substring(0, i) + word.substring(i + 1);
                if(map.containsKey(prev)){
                    map.put(word, Math.max(map.get(word), map.get(prev) + 1));
                }
            }
            ans = Math.max(ans, map.get(word));
        }

        return ans;
    }
}