leetcode1048

àì夳堔傛蜴生んèń 2021-12-19 04:13 132阅读 0赞

1 class Solution:
     2     def __init__(self):
     3         self.dp = {}
     4 
     5     def backtrack(self,word,subword):
     6         self.dp[word] = max(self.dp[word],self.dp[subword]+1)
     7         for j in range(len(subword)):
     8             subword2 = subword[:j] + subword[j+1:]
     9             if subword2 in self.dp.keys() and self.dp[subword2] == 0:
    10                 self.backtrack(subword,subword2)
    11 
    12     def longestStrChain(self, words: 'List[str]') -> int:
    13         n = len(words)
    14         words = sorted(words,key=lambda x:len(x))
    15         for i in range(n):
    16             word = words[i]
    17             self.dp[word] = 0
    18 
    19         for word in self.dp.keys():
    20             for j in range(len(word)):
    21                 subword = word[:j] + word[j+1:]
    22                 if subword in self.dp.keys():
    23                     if self.dp[subword] == 0:
    24                         self.backtrack(word,subword)
    25                     else:
    26                         self.dp[word] = max(self.dp[word],self.dp[subword]+1)
    27             if self.dp[word] == 0:
    28                 self.dp[word] = 1
    29         return max(self.dp.values())

本题是思路是使用动态规划，dp是一个字典，其含义是：假设以某个string作为链的结尾时形成的链的最大长度。

因此最后dp的values中，最大的值就是输入列表所能形成的最长的链的长度。

转载于:https://www.cnblogs.com/asenyang/p/10928401.html

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT甲级1048 Find Coins

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

朱雀/ 2023年07月24日 14:33/ 0 赞/ 97 阅读

相关 leetcode1048最长字符串链

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

青旅半醒/ 2023年01月21日 03:26/ 0 赞/ 56 阅读

相关 1048. 数字加密(20) python篇

1048. 数字加密(20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard

本是古典何须时尚/ 2022年10月01日 02:51/ 0 赞/ 128 阅读

相关杭电1048

The Hardest Problem Ever Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/3

心已赠人/ 2022年09月17日 03:04/ 0 赞/ 153 阅读

相关 PDSOJ 1048 Fibonacci Numbers(大数)

[Fibonacci Numbers][] 时间限制: 1 Sec 内存限制: 128 MB 提交: 13 解决: 2 \[ [提交][Link 1]\]

淡淡的烟草味﹌/ 2022年06月17日 00:49/ 0 赞/ 114 阅读

相关 1048. Find Coins (25)

Eva loves to collect coins from all over the universe, including some other planets like

妖狐艹你老母/ 2022年05月31日 12:44/ 0 赞/ 130 阅读

相关 1048. 数字加密(20)

本题要求实现一种数字加密方法。首先固定一个加密用正整数A，对任一正整数B，将其每1位数字与A的对应位置上的数字进行以下运算：对奇数位，对应位的数字相加后对13取余——这里用J代

墨蓝/ 2022年05月26日 07:37/ 0 赞/ 128 阅读

相关 1048 数字加密java答案

这道题我一开始以为是从前开始奇数和偶数位计算，结果它是从最后一位开始，这道题A和B哪个小了都需要从前补0，题目理解花了很长的时间 import java.io.Buf

骑猪看日落/ 2022年02月19日 02:59/ 0 赞/ 155 阅读

相关 leetcode1048

1 class Solution: 2 def __init__(self): 3 self.dp = {} 4

àì夳堔傛蜴生んèń/ 2021年12月19日 04:13/ 0 赞/ 133 阅读

相关 PAT~乙级~1048 数字加密 ~python

题目描述：本题要求实现一种数字加密方法。首先固定一个加密用正整数 A，对任一正整数 B，将其每 1 位数字与 A 的对应位置上的数字进行以下运算：对奇数位，对应位的数字相加

心已赠人/ 2021年11月27日 02:58/ 0 赞/ 196 阅读