hongtaoh

# This Gist is based on https://gist.github.com/rogerallen/1583593 by Roger Allen
#
# United States of America Julia Dictionary to translate States,
# Districts & Territories to Two-Letter codes and vice versa.
#
# https://gist.github.com/hongtaoh/69b607623d39341466bca33ba7fd9ab0
#
# Dedicated to the public domain.  To the extent possible under law,
# Hongtao Hao has waived all copyright and related or neighboring
# rights to this code.

hongtaoh

# BFS 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque 

        graph = defaultdict(list)
        for course, prereq in prerequisites:
            graph[prereq].append(course)
        
        # calculate in-degree

hongtaoh

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # dfs, recurssion
        if not grid:
            return 0 
        
        rows, cols = len(grid), len(grid[0])
        result = 0 

        def dfs(r, c):

hongtaoh

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {"(":")", "{":"}", "[":"]"}
        stack = []
        # we know all char in s is either key or value in dic
        for i in s:
            # if key, store in stack
            if i in dic:
                stack.append(i)
            # if value, check whether there is corresponding key

hongtaoh

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True 
            if (r<0 or c<0 or r>= ROWS or c>= COLS
            or board[r][c] != word[i] or

hongtaoh

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        for i in s:
            if i != "]":
                stack.append(i)
            else:
                substring = ""
                while stack[-1] != "[":

hongtaoh

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        left = 0 
        maxLen = 0
        for right in range(len(s)):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
            charSet.add(s[right])

hongtaoh

class Solution:
  # the most straightforward implementation
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        short_str, long_str = (str1, str2) if len(str1) <= len(str2) else (str2, str1)
        l = 0
        while l < len(short_str):
            r = len(short_str)
            while r >l and r <= len(short_str):
                substr = short_str[l:r]
                substr_len = r - l

hongtaoh

class Solution:
  # dynamic programming
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1
        for _ in range(n-1):
            temp = one 
            one += two
            two = temp
        return one

hongtaoh

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.binSearch(nums, target, True)
        right = self.binSearch(nums, target, False)
        return [left, right]
      
    # modified binary search algorithm
    def binSearch(self, nums, target, leftBiased):
        l = 0
        r = len(nums) - 1