2020年3月25日 星期三

[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_2word_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
  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)
  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)

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...