2020年3月25日 星期三

[LeetCode] Medium - 227. Basic Calculator II (G,M,A,F)

Source From Here
Question
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:
Input: "3+2*2"
Output: 7

Example 2:
Input: " 3/2 "
Output: 1

Example 3:
Input: " 3+5 / 2 "
Output: 5

Note:
* You may assume that the given expression is always valid.
* Do not use the eval built-in library function.

Solution

Naive (Timeout)
  1. class Solution:  
  2.     def calculate(self, s: str) -> int:  
  3.         stack = []  
  4.   
  5.         # 0) Building stack  
  6.         num = ''  
  7.         for c in s.strip():  
  8.             if c in ['+''-''*''/']:  
  9.                 stack.append(int(num))  
  10.                 stack.append(c)  
  11.                 num = ''  
  12.                 continue  
  13.             elif c == ' ':  
  14.                 continue  
  15.   
  16.             num += c  
  17.   
  18.         if num:  
  19.             stack.append(int(num))  
  20.           
  21.         def index_of(i):  
  22.             for j in range(i, len(stack)):  
  23.                 if stack[j] in ['*''/']:  
  24.                     return j  
  25.   
  26.             return -1  
  27.   
  28.         # 1) Start calculation  
  29.         # 1.1) Handle high priority op (/,*)  
  30.         i = index_of(0)  
  31.         while i > 0:  
  32.             hop = stack[i]  
  33.             num1 = stack[i-1]  
  34.             num2 = stack[i+1]              
  35.             if hop == '/':  
  36.                 stack[i-1:i+2] = [num1//num2]  
  37.             else:  
  38.                 stack[i-1:i+2] = [num1*num2]  
  39.   
  40.             i = index_of(i)  
  41.           
  42.         # 1.2) Handle low priority op (+/-)  
  43.         while len(stack) > 1:  
  44.             num1 = stack.pop(0)  
  45.             op = stack.pop(0)  
  46.             num2 = stack.pop(0)  
  47.             if op == '+':  
  48.                 stack.insert(0, num1 + num2)  
  49.             else:  
  50.                 stack.insert(0, num1 - num2)  
  51.   
  52.         # 2) Return the final result  
  53.         return stack[0]  
Discussion - Python 3, Runtime 76ms, Stack Approach (link)
  1. class Solution:  
  2.     def calculate(self, s: str) -> int:  
  3.         num, preop, stack = '''+', []  
  4.   
  5.         for c in s+'+':  
  6.             if c.isdigit():  
  7.                 num += c  
  8.             elif c == ' ':  
  9.                 continue  
  10.             elif num != '':  
  11.                 if preop == '+':  
  12.                     stack.append(int(num))  
  13.                 elif preop == '-':  
  14.                     stack.append(int(num) * -1)  
  15.                 elif preop == '*':  
  16.                     stack.append(int(num) * stack.pop())  
  17.                 else:  
  18.                     stack.append(math.trunc(stack.pop()/int(num)))  
  19.   
  20.                 num = ''  
  21.                 preop = c  
  22.   
  23.         return sum(stack)  
Runtime: 72 ms, faster than 92.89% of Python3 online submissions for Basic Calculator II.
Memory Usage: 14.6 MB, less than 88.89% of Python3 online submissions for Basic Calculator II.

Supplement
Leetcode: 227 Basic Calculator II 讲解 (Cspiration 官方频道)

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

[LeetCode] Medium - 227. Basic Calculator II (G,M,A,F)

Source From  Here Question Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-nega...