[LeetCode] Medium - 1048. Longest String Chain (G)

Source From Here
Question
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: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:

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

Solution

Naive

view plaincopy to clipboardprint?

1. from collections import defaultdict  
2.   
3. class Solution:  
4.     def longestStrChain(self, words: List[str]) -> int:  
5.         # 0) Preprocess  
6.         wdict = defaultdict(list) # key as length of word; value as list of word  
7.         for w in words:  
8.             w_len = len(w)  
9.             wdict[w_len].append(''.join(sorted(list(w))))  
10.   
11.         # 1) Start algorithm  
12.         max_wc = 1  
13.         ''' longest word chain'''  
14.           
15.         def is_one_char_away(w, nw):  
16.             nw_i = 0  
17.             try:  
18.                 for i in range(len(w)):  
19.                     if w[i] == nw[nw_i]:  
20.                         nw_i += 1  
21.                     elif w[i] == nw[nw_i+1]:  
22.                         nw_i += 2  
23.                     else:  
24.                         return False  
25.             except:  
26.                 return False  
27.   
28.             return True  
29.   
30.         visited_wc = set()  
31.         def search_wc(w_len, w, wc):  
32.             wc_len = len(wc)  
33.             next_w_len = w_len + 1  
34.             for nw in wdict[next_w_len]:  
35.                 if is_one_char_away(w, nw):  
36.                     new_wc = []  
37.                     new_wc.extend(wc)  
38.                     new_wc.append(nw)  
39.                     _wc_len = search_wc(next_w_len, nw, new_wc)  
40.                     if _wc_len > wc_len:  
41.                         wc_len = _wc_len  
42.   
43.             return wc_len  
44.   
45.         for w_len in sorted(wdict.keys())[:-1]:  
46.             for w in wdict[w_len]:  
47.                 wc_len = search_wc(w_len, w, [w])  
48.                 if wc_len > max_wc:  
49.                     max_wc = wc_len  
50.   
51.         return max_wc  

Runtime: 404 ms, faster than 25.51% of Python3 online submissions for Longest String Chain.
Memory Usage: 14.5 MB, less than 100.00% of Python3 online submissions for Longest String Chain.

Discussion: dp soluiton (link)

view plaincopy to clipboardprint?

1. from collections import defaultdict  
2.   
3. class Solution:  
4.     def longestStrChain(self, words: List[str]) -> int:  
5.         words = sorted(words,key=lambda x:len(x))  
6.         dp = [1]*len(words)  
7.         record = {}  
8.         for i, word in enumerate(words):  
9.             for j in range(len(word)):  
10.                 predecessor = word[:j]+word[j+1:]  
11.                 if predecessor in record:  
12.                     dp[i] = max(dp[record[predecessor]]+1,dp[i])  
13.             record[word] = i  
14.         return max(dp)  

Runtime: 120 ms, faster than 90.98% of Python3 online submissions for Longest String Chain.
Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Longest String Chain.

Supplement
* 知呼 - 1048. Longest String Chain
* LeetCode 1048. Longest String Chain Explanation and Solution (happygirlzt)