首页 > 其他 > 详细

1048. Longest String Chain (M)

时间:2021-05-18 09:03:54      阅读:22      评论:0      收藏:0      [点我收藏+]

Longest String Chain (M)

题目

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: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

Constraints:

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

题意

如果字符串s2能够通过在字符串s1的某一个位置插入一个字符后得到,那么说s1是s2的"前辈"。给定一个字符串数组,从中选取若干个组成一个序列,使该序列中每一个字符串都是后一个字符串的前辈,求这样的序列的最大长度。

思路

动态规划。将数组按照字符串长度排序,问题就变得和LIS问题类似,使用相同的方法解决即可。


代码实现

Java

class Solution {
    public int longestStrChain(String[] words) {
        int ans = 0;
        int[] dp = new int[words.length];
        Arrays.fill(dp, 1);
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        for (int i = 1; i < words.length; i++) {
            for (int j = 0; j < i; j++) {
                if (judge(words[j], words[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }

    private boolean judge(String a, String b) {
        if (a.length() +1!= b.length()) return false;

        int i = 0, j = 0;
        while (i < a.length() && j < b.length()) {
            if (a.charAt(i) == b.charAt(j)) i++;
            j++;
        }

        return i == a.length() && b.length() - j <= 1;
    }
}

1048. Longest String Chain (M)

原文:https://www.cnblogs.com/mapoos/p/14778914.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!