Intuition Compute values on the fly, use stack for brackets. Approach Parse each number, use num = 10xnum + current. Keep track of the last sign (starts as positive). When an opening bracket is found, stack the item and the sign. When a closing bracket is found, pop sign and item and do the math. Complexity Time complexity: O(N) Space complexity: O(N) Code class Solution(object): def calculate(self, s): """ :type s: str :rtype: int """ stack = [] res = 0 num = 0 sign = 1 for c in s: if c.isdigit(): num = (num * 10 ) + int(c) elif c == "+": res += sign * num sign = 1 num = 0 elif c == "-": res += sign * num sign = -1 num = 0 elif c == "(": stack.append(res) stack.append(sign) sign = 1 res = 0 elif c == ")": res += sign * num res *= stack.pop() # sign res += stack.pop() # num num = 0 return res + sign * num

Intuition Use a stack to pile all numbers, when an operator is found, pop the last two numbers, do the calculation and then push it to the stack again. Assuming the expression is valid, at the end thre will be only one element in the stack that is the result. Approach Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] for t in tokens: if self.is_op(t): right = stack.pop() left = stack.pop() if t == "/": stack.append(self.div(left , right)) elif t == "*": stack.append(left * right) elif t == "+": stack.append(left + right) elif t == "-": stack.append(left - right) else: stack.append(int(t)) return stack[0] def div(self, left, right): r = left / right if r < 0 and right * r != left: return r + 1 return r def is_op(self, token): return token == "/" or token == "*" or token == "+" or token == "-"

Intuition Use a stack to keep current element and current_min Approach Use a stack to keep current element and current_min Complexity Time complexity: O(1) Space complexity: O(n) Code class MinStack(object): def __init__(self): self.stack = [] self.min = float('inf') def push(self, val): """ :type val: int :rtype: None """ self.min = min(val, self.min) item = { "val": val, "min": self.min } self.stack.append(item) def pop(self): """ :rtype: None """ self.stack.pop() if len(self.stack) > 0: self.min = self.stack[-1]['min'] else: self.min = float('inf') def top(self): """ :rtype: int """ return self.stack[-1]["val"] def getMin(self): """ :rtype: int """ return self.min

Intuition Split path by /, use a stack to push or pop elements. Approach Split the absolute path by ‘/’. For each element If it’s empty, skip If it’s ., skip If it’s .. and the stack has element, pop Else push to the stack Concat everything and return Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def simplifyPath(self, path): """ :type path: str :rtype: str """ dirs = [] for d in split(path, "/"): if len(d) == 0: continue if d == ".": continue if d == "..": if len(dirs) > 0: dirs.pop() else: dirs.append(d) return "/" + "/".join(dirs)

Intuition Map characters letters, and map seen letters. Approach We will need to use two use two structures here. One to map the correspoding character One to keep track of seen chracters, this is necessary becase “no two chracter may map to the same character” If len is diff, just return false. Loop through the chracters (s -> cs, t -> ct). if cs was mapped before, and map[cs] == ct, move to the next if cs was mapped before, and map[cs] != ct, return False if cs was not mapped before, and seen[ct], return False else map[cs] = ct, and seen[ct] = True Complexity Time complexity: O(n) ...