1048. Longest String Chain

Question

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

word<sub>A</sub> is a predecessor of word<sub>B</sub> if and only if we can insert exactly one letter anywhere in word<sub>A</sub> without changing the order of the other characters to make it equal to word<sub>B</sub>.

• For example, "abc" is a predecessor of "ab<u>a</u>c", while "cba" is not a predecessor of "bcad".

A word chain* *is a sequence of words [word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>] with k >= 1, where word<sub>1</sub> is a predecessor of word<sub>2</sub>, word<sub>2</sub> is a predecessor of word<sub>3</sub>, 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.

Solution

排序+动态规划。
采用一个一维动态规划数组记录到某个word的最大字符串链长度。

排序

每个predecessor必定比next少1，因此首先将数组根据word的长度排序。

动态规划

数组dp[i]记录到i位置时的最大长度。
双重遍历i和j，其中j>i。如果words[i-1]是words[j-1]的predecessor，则更新dp[j]为dp[j]与dp[i]+1的较大值。

辅助方法 isValid()

判断predecessor是否有效。
初始化一个flag为false记录不同字符是否已出现。
如果两者长度差不为1直接返回false。
双指针分别指向两个字符串，如果两个当前字符相等，则两个指针共同前进。
如果不相等且flag为true则i指针前进，并且将flag改为false。否则返回false。
如果循环结束返回true。

Code

class Solution {
    public int longestStrChain(String[] words) {
        int max = 0;
        Arrays.sort(words, (a,b) -> a.length() - b.length());
        int[] dp = new int[words.length+1];
        for(int i = 1; i <= words.length; i++){
            for(int j = i + 1; j <= words.length; j++){
                if(isValid(words[i-1], words[j-1])){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private boolean isValid(String predecessor, String next){
        if(predecessor.length() + 1 != next.length()) return false;
        boolean flag = true;
        int i = 0, j = 0;
        while(i < next.length() && j < predecessor.length()){
            if(next.charAt(i) == predecessor.charAt(j)){
                i++;
                j++;
            }
            else if(flag){
                i++;
                flag = false;
            }
            else{
                return false;
            }
        }
        return true;
    }
}