[LeetCode] 214. Shortest Palindrome

Problem : https://leetcode.com/problems/shortest-palindrome/

The quiz asks to add character only in front of the original string.

That means the characters be added in front must come from the end of the string and in reversed order. 

Generally it is the form of   [R'] + [Palindrome] + [R].

R' = reversed R

Let S' = revered S, then there must be S'[i:] == S[:Len(S) - i].  The answer is adding the longest S'[0:i] in front of S

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        r = s[::-1]
        
        for i in range(len(s)):
            if r[i:] == s[:len(s)-i]:
                return r[:i] + s
        
        return s

[LeetCode] 213. House Robber II

 Problem : https://leetcode.com/problems/house-robber-ii/

Since the first and the last house are exclusive to each other. 

We can break it into 2 cases:

- Start from the first house and end at the 2nd from the last house.

- Start from the 2nd house and end at the last house.

The answer is the max value of the 2 cases.

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        @lru_cache(maxsize = None)
        def helper(i, end, safe):
            """
            i : current house
            end: last house index
            safe: safe to rob
            """
            if i == end:
                return 0
            
            stolen = 0
            
            if safe:
                stolen = max(nums[i] + helper(i+1, end, False), helper(i+1, end, True))
            else:
                stolen = helper(i+1, end, True)
            
            return stolen
        
        if not nums:
            return 0
        
        if len(nums) < 2:
            return max(nums)
        
        return max(helper(0, len(nums) - 1, True), helper(1, len(nums), True))

Bottom-Up approach

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        def helper(houses):
            steal = [0] * len(houses)
            steal[0] = houses[0]
            
            notSteal = [0] * len(houses)
            
            for i in range(1, len(houses)):
                steal[i] = notSteal[i-1] + houses[i]
                notSteal[i] = max(notSteal[i-1], steal[i-1])
          
            return max(steal[-1], notSteal[-1])
        
        if not nums:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        if len(nums) == 2:
            return max(nums[0], nums[1])
        
        return max(helper(nums[1:]), helper(nums[:-1]))

[LeetCode] 212. Word Search II

Problem : https://leetcode.com/problems/word-search-ii/

Tire + Backtracking approach :

class Node:
    def __init__(self, val='', end=False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:
    def __init__(self):
        self.root = Node()
    
    def add(self, word):
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
            
        p.end = True
        

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROW = len(board)
        COLUMN = len(board[0])
        
        trie = Trie()
        
        for word in words:
            trie.add(word)
        
        result = set()
        visited = [[False] * COLUMN for _ in range(ROW)]
        
        def dfs(y, x, tmp, p):
            if p.end:
                result.add(tmp)
            
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ny, nx = y + dy, x + dx
                
                if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx] and board[ny][nx] in p.nxt:
                    visited[ny][nx] = True
                    dfs(ny, nx, tmp + board[ny][nx], p.nxt[board[ny][nx]])
                    visited[ny][nx] = False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] in trie.root.nxt:
                    visited[y][x] = True
                    dfs(y, x, board[y][x], trie.root.nxt[board[y][x]])
                    visited[y][x] = False
        
        return result

Edited on 10/9/2021. Update for simpler code.

[LeetCode] 211. Design Add and Search Words Data Structure

 Problem : https://leetcode.com/problems/design-add-and-search-words-data-structure/

Trie ( prefix tree ) approach : 

class Node:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False
            
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.trie = Node()
        self.maxLen = 0
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        
        self.maxLen = max(self.maxLen, len(word))
        p = self.trie
        
        for w in word:
            if w in p.children:
                p = p.children[w]
            else:
                tmp = Node(w)
                p.children[w] = tmp
                p = tmp
            
        p.end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        
        def dfs(i, p):
            if i >= len(word):
                return p.end
            
            w = word[i]
                
            if w == '.':
                for k in p.children:
                    if dfs(i + 1, p.children[k]):
                        return True
                    
            elif w in p.children:
                return dfs(i + 1, p.children[w])
                    
            return False
        
        return dfs(0, self.trie) if len(word) <= self.maxLen else False

[LeetCode] 210. Course Schedule II

Problem : https://leetcode.com/problems/course-schedule-ii/

Topological sort approach.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        
        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1
        
        
        noindegree = deque()
        
        for i in range(numCourses):
            if indegree[i] == 0:
                noindegree.append(i)
        
        result = []
        
        while noindegree:
            picked = noindegree.popleft()
            
            result.append(picked)
            
            for course in graph[picked]:
                indegree[course] -= 1
                
                if indegree[course] == 0:
                    noindegree.append(course)
        
        return result if len(result) == numCourses else []

[LeetCode] 209. Minimum Size Subarray Sum

 Problem : https://leetcode.com/problems/minimum-size-subarray-sum/

Sliding-window approach.

Time Complexity = O ( N )

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        MAX_INT = 2 ** 31 - 1
        result = MAX_INT
        right = 0
        sums = 0
        
        for left in range(len(nums)):
            while right < len(nums) and sums < s:
                sums += nums[right]
                right += 1
            
            if sums >= s:
                result = min(result, right - left)
            
            sums -= nums[left]
        
        return result if result != MAX_INT else 0

[LeetCode] 208. Implement Trie (Prefix Tree)

Problem : https://leetcode.com/problems/implement-trie-prefix-tree/

One node of Trie represents a letter of the inserted words.

To search an inserted word, the code travels from the root node and find if current letter is represented by one of the child node.  When reach to the last letter of the given word, check if  Node.end = True.

class Node:
    def __init__(self, val = '', end = False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:

    def __init__(self):
        self.root = Node()
        
    def insert(self, word: str) -> None:
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
        
        p.end = True
                
    def search(self, word: str) -> bool:
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                return False
            p = p.nxt[w]
        
        return p.end

    def startsWith(self, prefix: str) -> bool:
        p = self.root
        
        for w in prefix:
            if w not in p.nxt:
                return False
            p = p.nxt[w]
        
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Edited on 10/08/2021. Tidy the implementation.

[LeetCode] 207. Course Schedule

 Problem : https://leetcode.com/problems/course-schedule/

Topological Sort

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        
        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1
        
        noindegree = deque()
        
        for i in range(numCourses):
            if indegree[i] == 0:
                noindegree.append(i)
            
        totalPicked = 0
        
        while noindegree:
            picked = noindegree.popleft()
            
            totalPicked += 1
            
            for course in graph[picked]:
                indegree[course] -= 1
                
                if indegree[course] == 0:
                    noindegree.append(course)
        
        return totalPicked == numCourses

[LeetCode] 206. Reverse Linked List

 Problem : https://leetcode.com/problems/reverse-linked-list/

The recursive solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            # do not reverse empty list or single element list
            return head
        
        # reverse list starts with the tail element
        tail = head.next
        new_head = self.reverseList(tail)
        
        # append the previous head to the tail
        tail.next = head
        head.next = None
        
        # return the new head
        return new_head

The iterative solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return None
        
        pre = head
        cur = head.next
        
        while cur:
            t = cur.next
            
            cur.next = pre
            pre = cur
            cur = t
        
        head.next = None
        return pre

Edited on 09/07/2021. Add the iterative solution.

[LeetCode] 205. Isomorphic Strings

 Problem : https://leetcode.com/problems/isomorphic-strings/

Because we can use any character to update s. Only the relative position of characters matters.

Use the first pos of one character to encode the input string. Then check if the 2 encoded strings are identical.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        def encode(word):
            seen = {}
           
            for i, x in enumerate(word):
                if x not in seen: 
                    seen[x] = i
                yield seen[x]
            
        
        return all(map(lambda x: x[0] == x[1], zip(encode(s), encode(t))))

Updated on 07/12/2021. Update for a simpler solution.

[LeetCode] 204. Count Primes

 Problem : https://leetcode.com/problems/count-primes/

class Solution:
    def countPrimes(self, n: int) -> int:
        
        isPrime = [True] * (n + 2)
        
        isPrime[0] = False
        isPrime[1] = False
        
        
        i = 2
        
        while i * i < n:
            if isPrime[i]:
                j = i * i
                while j < n:
                    isPrime[j] = False
                    j += i
            
            i += 1
        
        result = 0
        for i in range(n):
            if isPrime[i]:
                result += 1
        
        return result

[LeetCode] 203. Remove Linked List Elements

Problem : https://leetcode.com/problems/remove-linked-list-elements/

Remove element recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        
        if head.val == val:
            # remove element with the target val
            return self.removeElements(head.next, val)
        
        head.next = self.removeElements(head.next, val)
        
        return head

[LeetCode] 202. Happy Number

 Problem : https://leetcode.com/problems/happy-number/

class Solution:
    def isHappy(self, n: int) -> bool:
        # use hashset to avoid looping in a cycle
        seen = set()
        
        while n not in seen:
            seen.add(n)
            
            nextNum = 0
            
            while n:
                t = n % 10
                nextNum += t * t
                n = n // 10
            
            n = nextNum
            
            if n == 1:
                return True
        
        return False

[LeetCode] 201. Bitwise AND of Numbers Range

 Problem : https://leetcode.com/problems/bitwise-and-of-numbers-range/

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        
        mask = 0xFFFFFFFF
        
        while (m & mask) != (n & mask):
        
            # shift mask to left with one bit
            # to set m and n one more bit on right to 0
            mask <<= 1
        
        return m & mask

[LeetCode] 200. Number of Islands

 Problem : https://leetcode.com/problems/number-of-islands/

Use counter as flag to mark visited position.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        if not row:
            return 0
        
        column = len(grid[0])
        
        count = 2
        
        def dfs(y, x, mark):
            if y < 0 or y >= row:
                return
            
            if x < 0 or x >= column:
                return
            
            if grid[y][x] == "1":
                grid[y][x] = mark

                dfs(y-1, x, mark)
                dfs(y+1, x, mark)
                dfs(y, x-1, mark)
                dfs(y, x+1, mark)
            
        
        for y in range(row):
            for x in range(column):
                if grid[y][x] == "1":
                    dfs(y, x, str(count))
                    count += 1
        
        
        return count - 2

[LeetCode] 199. Binary Tree Right Side View

 Problem : https://leetcode.com/problems/binary-tree-right-side-view/

Use BFS to traverse the tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root : return []
        
        result = []
        
        queue = deque([root])
        while queue:
            N = len(queue)
            for i in range(N):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                    
                if node.right:
                    queue.append(node.right)
                
                # append the right-most node value
                if i == N-1:
                    result.append(node.val)
                    
        return result

DFS Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        
        if not root: return []
        
        result = []
        
        # dfs
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append(node.val)
            
            if node.left:
                stack.append((node.left, level+1))
                
            if node.right:
                stack.append((node.right, level+1))
                    
        return result

Edited on 05/31/2021. Add DFS solution.

[LeetCode] 198. House Robber

 Problem : https://leetcode.com/problems/house-robber/

Robber has 2 choices for each house,  steal this house if the previous house is not be stolen or not steal this house.

DP solution

Time Complexity = O ( N )

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        steal = [0] * len(nums)
        notSteal = [0] * len(nums)
        
        steal[0] = nums[0]
       
        for i in range(1, len(nums)):
            steal[i] = notSteal[i-1] + nums[i]
            notSteal[i] = max(notSteal[i-1], steal[i-1])
            
        return max(steal[-1], notSteal[-1])

Another DP solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            # max(not-rob-house-i, rob-house-i)
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        return dp[-1]

Memorization solution

Time Complexity =  O ( N ).  

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        @lru_cache(maxsize = None)
        def dfs(i, safe):
            if i >= len(nums):
                return 0
            
            s1 = nums[i] + dfs(i+1, False) if safe else 0
            s2 = dfs(i+1, True)
            
            return max(s1, s2)
        
        
        return dfs(0, True)

[LeetCode] 191. Number of 1 Bits

Problem : https://leetcode.com/problems/number-of-1-bits/

An one liner solution:

Time Complexity = O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([n >> offset & 1 for offset in range(32)])

Use bit manipulate trick to only count '1'

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        while n:
            result += 1
            n = n & (n-1)
        
        return result

A divide and conquer approach. And use memorization to accelerate. ( The fastest solution. )

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #000 001 010 011 100 101 110 111
    
        @cache
        def helper(x):
            return helper(x >> 3) + helper(x & 7) if x > 7 else [0, 1, 1, 2, 1, 2, 2, 3][x]
                
        return helper(n)

Edited on 05/04/2021. Add the only count '1' solution.

Edited on 05/04/2021. Add the divide and conquer solution.

[LeetCode] 190. Reverse Bits

 Problem : https://leetcode.com/problems/reverse-bits/

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        
        for i in range(32):
            result = result << 1
            result = result | ((n >> i) & 1)
           
        return result

[LeetCode] 189. Rotate Array

 Problem : https://leetcode.com/problems/rotate-array/

A solution uses separate cache.

Time Complexity = O ( N )

Space Complexity = O ( N )

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        offset = len(nums) - (k % len(nums))
        
        tmp = nums[offset:] + nums[:offset]
        
        for i in range(len(nums)):
            nums[i] = tmp[i]

Reverse 3 times solution:

Time Compelxity = O ( N )

Space Complexity = O ( 1 )

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            
        
        N = len(nums)
        pivot = N - k % N
        
        # reverse the left side of pivot
        reverse(0, pivot-1)
        # reverse the right side of pivot
        reverse(pivot, N-1)
        # reverse the entire array
        reverse(0, N-1)

[LeetCode] 188. Best Time to Buy and Sell Stock IV

 Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

On each day, it has 2 states.

1. Buy stock. ( Buy stock on current day or bought stock on previous days )

2. Sell stock. ( Sell stock on current day or sold stock on previous days )

The answer is max profit can get if sell stock on last day.

Top-Down solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        buy, sell = 0, 1
        
        @lru_cache(maxsize = None)
        def dp(i, state, transaction):
            if state == buy and transaction == 0:
                # cannot buy when transaction == 0
                return -2 ** 31
            
            if state == sell and transaction == 0:
                # no profit when transaction == 0 
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == sell:
                return 0
            
            if state == buy:
                # max( profit-of-buy-on-day-i [descrease transaction for selling on previous days], 
                #      profit-of-bought-on-previous-days )
                return max(-1 * prices[i] + dp(i-1, sell, transaction - 1), dp(i-1, buy, transaction))
            
            if state == sell:
                # max( profit-of-sell-on-day-i, profit-of-sold-on-previous-days )
                return max(prices[i] + dp(i-1, buy, transaction), dp(i-1, sell, transaction))
    
        if len(prices) <= 1:
            return 0
        
        # unlimited transaction when k is more than half of the amount of prices
        if k >= len(prices) // 2:
            profit = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        return dp(len(prices)-1, sell, k)

Bottom-Up solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        if n <= 1:
            return 0
        
        # unlimited transaction when k is more than half of prices
        if k >= n  // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        # dp[n][k+1][2]
        dp = [[[0, 0] for _ in range(k+1)] for _ in range(n)] 
        
        for i in range(n):
            dp[i][0][0] = 0  # sell on day i, transaction 0 
            dp[i][0][1] = -2 ** 31 # buy on day i, transaction 0 (impossible case)
        
        for j in range(1, k+1):
            dp[0][j][0] = 0
            dp[0][j][1] = -prices[0]
        
        for i in range(1, n):
            for j in range(1, k+1):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
        
        return dp[-1][-1][0]

[LeetCode] 187. Repeat DNA Sequences

Problem : https://leetcode.com/problems/repeated-dna-sequences/

Find all 10-letter-long sequences and save into hash table.

Return sequences which's counter > 1.

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seen = defaultdict(int)
        
        for i in range(len(s) - 10 + 1):
            seen[s[i:i+10]] += 1
        
        return filter(lambda k: seen[k] > 1, seen.keys())