Algorithm - Stack (1)

Leetcode Stack Problem Collection (1)

• 20.Valid Parentheses
• 1249.Minimum Remove to Make Valid Parentheses
• 394.Decode String
• 1209.Remove All Adjacent Duplicates in String II
• 739.Daily Temperatures
• 1. Simplify Path

20. Valid Parentheses

def isValid(self, s: str) -> bool:
    right = {
        ')': '(',
        '}': '{', 
        ']': '['
    }
    stack = []
    for c in s:
        # left bracket
        if c not in right:
            stack.append(c)
        # right bracket
        elif not stack or stack.pop() != right[c]:
            return False
    return not stack

1249. Minimum Remove to Make Valid Parentheses

• for right bracket, must match to an existed left bracket, or remove it.
• for left bracket, log its index
  After scan the whole string, remove open left bracket

  def minRemoveToMakeValid(self, s: str) -> str:
      open_left = []
      res = ''
      for c in s:
          if c == '(':
              res += c
              open_left.append(len(res) - 1)
          elif c == ')':
              if open_left:
                  res += c
                  open_left.pop()
          else:
              res += c
      for i in reversed(open_left):
          res = res[:i] + res[i + 1: ]
      return res

394. Decode String

def decodeString(self, s: str) -> str:
    stack = []
    for c in s:
        if c == ']':
            repeat = ''
            while stack:
                x = stack.pop()
                
                # found substring
                if x == '[':
                    # find number
                    num = ''
                    while stack and stack[-1].isdigit():
                        num = stack.pop() + num
                    num = int(num)
                    repeat = repeat * int(num)
                    stack.append(repeat)
                    break
                repeat = x + repeat
        else:
            stack.append(c)
            
    return ''.join(stack)

1209. Remove All Adjacent Duplicates in String II

def removeDuplicates(self, s: str, k: int) -> str:
    stack = []  # (element, cnt)
    for c in s:
        if stack and c == stack[-1][0]:
            cnt = stack[-1][1] + 1
            stack.append((c, cnt))
            if cnt == k:
                for _ in range(k):
                    stack.pop()
        else:
            stack.append((c, 1))
    return ''.join([x[0] for x in stack])

739. Daily Temperatures

use index to calculate days

def dailyTemperatures(self, T: List[int]) -> List[int]:
    stack = []  # temp, index
    warmer = [0] * len(T)
    for i, temp in enumerate(T):
        while stack and temp > stack[-1][0]:
            pre_temp, j = stack.pop()
            warmer[j] = i - j
        stack.append((temp, i))
    return warmer

71. Simplify Path

def simplifyPath(self, path: str) -> str:
    stack = []
    paths = path.split('/')
    for p in paths:
        if p == '..':
            if stack:
                stack.pop()
            continue
        elif p == '.' or p == '':
            continue
        else:
            stack.append(p)
    return '/' + '/'.join(stack)