Keep creating , Accelerate growth ！ This is my participation 「 Nuggets day new plan · 6 Yuegengwen challenge 」 Of the 34 God , Click to see the event details
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.
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.
Note:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of lowercase English letters.
According to the meaning , Given an array of words , Each word is made up of lowercase English letters .
wordA yes wordB If and only if we can wordA Insert a letter exactly at any position of the without changing the order of the other characters so that it is equal to wordB.
A word chain is a word sequence [word1, word2, ..., wordk] , among k >= 1, among word1 yes word2 The forerunner of ,word2 yes word3 The forerunner of , And so on . Returns the length of the longest possible word chain for a word selected from a given word list .
This is a typical dynamic programming problem , Because this chain has a length limit , So first we will words Sort in ascending order , So we can, with the length limit , Use a double loop to find the longest word chain length that can be formed by the subarray one by one . We define a one-dimensional array dp ,dp[i] Represents an index i The word is the longest length of the word chain at the end , If two words words[j] and words[i] In line with the question , Then update dp[i]= max(dp[i], dp[j]+1) . After traversal, it returns directly to dp The maximum value in the .
The time complexity is O(16*N^2) , The space complexity is O(N^2) .
class Solution(object):
def longestStrChain(self, words):
"""
:type words: List[str]
:rtype: int
"""
def check(s1, s2):
M, N = len(s1), len(s2)
if M + 1 != N:
return False
i, j = 0, 0
while i < M and j < N:
if s1[i] == s2[j]: i += 1
j += 1
return i == M
words.sort(key=lambda x: (len(x), x))
N = len(words)
dp = [1] * N
for i in range(N):
for j in range(i):
if check(words[j], words[i]):
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
Runtime: 3021 ms, faster than 5.56% of Python online submissions for Longest String Chain.
Memory Usage: 14.2 MB, less than 24.50% of Python online submissions for Longest String Chain.
leetcode.com/problems/lo…
Your support is my greatest motivation
