Leetcode submissions week 1

Hard Problem :

10. Regular Expression Matching

# Dynamic programming # Bottom up approach # Python

Code :

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        res = [[False for i in range(len(p)+1)] for j in range(len(s)+1)] 
        res[0][0] = True
        
        # Look 2 behind for occurence of a start
        # Looking only at pattern fills the top row
        for i in range(1, len(p)+1):
            if p[i-1] == "*":
                res[0][i] = res[0][i-2]
                
        # for all subsequent rows
        for i in range(1, len(s)+1):
            for j in range(1, len(p)+1):
                # i is pointer to char in s
                # j is pointer to char in j
                
                # if patter previous character is *
                if p[j-1] == "*":
                    # check if j-2th character is . or equal to previous character in s
                    if p[j-2] == "." or p[j-2]==s[i-1]:
                        # assign value of j-2th res entry or jth entry of shortened result
                        res[i][j] = res[i][j-2] or res[i-1][j]
                    else:
                        # indicates zero occurence of j-2th character
                        res[i][j] = res[i][j-2]
                # if previous character is . or equal to previous character in string
                elif p[j-1] == "." or p[j-1]==s[i-1]:
                    # assign to previous character in shortened result 
                    res[i][j] = res[i-1][j-1]
                else:
                    # assign false since none of the above conditions matched
                    res[i][j] = False
                    
        # result is the bottom right element of the table            
        # Complexity len(s) * len(p) ~ i**2
        return res[len(s)][len(p)]

11. Container with the most water

# Array # 2 pointers # Python

Code :

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        left = 0
        right = len(height) - 1
        max_area = 0
        while left < right:
            if height[left] < height[right]:
                current_area = height[left] * (right - left)
                left += 1
            elif height[right] < height[left]:
                current_area = height[right] * (right - left)
                right -= 1
            else:
                current_area = height[right] * (right - left)
                left += 1
                right -= 1
            
            max_area = max_area if max_area > current_area else current_area
        return max_area

200. Number of Islands

# Depth First Search # def dfsUtil # Python

Code :

class Solution:
    
    def dfsUtil(self, loc):
        self.visited.add(loc)
        if loc[0] < 0 or loc[1] < 0 or loc[0] >= len(self.grid) or loc[1] >= len(self.grid[0]) or self.grid[loc[0]][loc[1]] == "0":
            return []
        elif self.hashmap.get(loc):
            return self.hashmap.get(loc)
        else:
            # print(self.grid[loc[0]][loc[1]])
            result = []
            result.extend(self.dfsUtil((loc[0]-1, loc[1]))) if (loc[0]-1, loc[1]) not in self.visited else []
            result.extend(self.dfsUtil((loc[0], loc[1]-1))) if (loc[0], loc[1]-1) not in self.visited else []
            result.extend(self.dfsUtil((loc[0]+1, loc[1]))) if (loc[0]+1, loc[1]) not in self.visited else []
            result.extend(self.dfsUtil((loc[0], loc[1]+1))) if (loc[0], loc[1]+1) not in self.visited else []
            result.append((loc[0], loc[1]))
            self.hashmap.update({loc: result})
            # print(result)
            return result
            
    
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.hashmap = {}
        self.visited = set((0, 0))        
        self.islands = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if (i, j) not in self.visited:
                    island_collection = self.dfsUtil((i, j))
                    if island_collection:
                        # print(i, j)
                        self.islands.append(island_collection)
                    
        return len(self.islands)

199. Binary Tree Right Side View

# Depth First Search # log(n) complexity # Python

Code :

class Solution:
    
    def helper(self, node, depth):
        if not node:
            return
        else:
            # Here the catch is comparing the current depth and the length of the output list
            # If both are same then we add else we dont
            if len(self.right_view_out) == depth: 
                self.right_view_out.append(node.val)
            self.helper(node.right, depth + 1)
            self.helper(node.left, depth + 1)
    
    def rightSideView(self, root: TreeNode) -> List[int]:
        self.right_view_out = []
        self.helper(root, 0)
        return self.right_view_out

198. House Robber

# Dynamic Programming # Similar to Cutting Rod # Python

Code :

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

965. Univalued Binary Tree

# Breadth First Search using Queues # Set # Value Counter # Python

Code :

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        output_list = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            if node:
                output_list.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
        value_count = len(set(output_list))
        if value_count == 1:
            return True
        else:
            return False