Leetcode 1048:最长字符串链(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1048:最长字符串链(超详细的解法!!!)

in leetcode with 0 comment

给出一个单词列表,其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1word2 的前身。例如,"abc""abac" 的前身。

词链是单词 [word_1, word_2, ..., word_k] 组成的序列,k >= 1,其中 word_1word_2 的前身,word_2word_3 的前身,依此类推。

从给定单词列表 words 中选择单词组成词链,返回词链的最长可能长度。

示例:

输入:["a","b","ba","bca","bda","bdca"]
输出:4
解释:最长单词链之一为 "a","ba","bda","bdca"。

提示:

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length <= 16
  3. words[i] 仅由小写英文字母组成。

解题思路

首先应该对words按照单词长度从小到大的顺序排序(结果字符串的长度是递增的)。接着需要思考长度为k的字符串到长度为k+1的字符串的过程。可以采用暴力的策略,枚举k+1长度字符串的所有长度为k的子串,同理枚举k长度字符串的所有长度为k-1的子串,以此类推。我们可以很容易的写出转移方程

其中$word_k$属于长度为[0,len(words))的字符串,并且$word_k$是$word_{k+1}$的前身,$f(k)$表示以长度为k字符串结尾的词链长度,对于中间产生的字符串可以通过字典存储。

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        mem = collections.defaultdict(int)
        for w in words:
            mem[w] = max(mem[w[:i] + w[i + 1:]] + 1 for i in range(len(w)))
        return max(mem.values())

当然上述做法比较粗暴,你也可以通过如下函数判断s1是不是s2的前身。

def isPreString(s1, s2):
    n, p, i = len(s1), 0, 0
    while i < n:
        if s1[i] != s2[i+p]:
            p += 1
            if p != 1:
                return False
            else:
                i -= 1
        i += 1
    return True

如果使用这种算法的话,算法的效率会更高。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses