Blog Feed – Page 32 – 步步发财

Word Squares – Python 3 (Week 12 – 19)

class Solution:
    """
    @param: words: a set of words without duplicates
    @return: all word squares
    """
        
    def initPrefix(self, words):
        for word in words:
            if '' not in self.hash:
                self.hash[''] = []
            self.hash[''].append(word)
            #self.hash[""] += [str(word)] 
                
            prefix = ''
            for c in word:
                prefix += c
                if prefix not in self.hash:
                    self.hash[prefix] = []
                self.hash[prefix].append(word)
                #self.hash[prefix] += [str(word)]
    
    def checkPrefix(self, x, nextWord, l):
        for i in range (x + 1, l):
            prefix = ''
            for item in self.path:
                prefix += item[i]
            prefix += nextWord[i]
            if prefix not in self.hash:
                return False
        return True
        
    def dfs(self, x, l):
        if x == l:
            self.ans.append(list(self.path)) #copy list
            #self.ans.append(self.path)
            return
        
        prefix = ""
        for item in self.path:
            prefix += item[x]
            
        for item in self.hash[prefix]:
            if not self.checkPrefix(x, item, l):
                continue
            self.path.append(item)
            self.dfs(x + 1, l)
            self.path.pop()
        
        
    def wordSquares(self, words):
        # write your code here
        self.hash = {}
        self.path = []
        self.ans = []
        
        if not words:
            return self.ans
        
        self.initPrefix(words)
        self.dfs(0, len(words[0]))
        
        return self.ans

Time O(n^m). Space O(n^m). n is length of dict. m is length of longest word.

Find Leaves of Binary Tree – Python 3 (Week 12 – 18)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param: root: the root of binary tree
    @return: collect and remove all leaves
    """
    def __init__(self):
        self.ans = []
        
    def findLeaves(self, root):
        # write your code here
        self.dfs(root)
        return self.ans
        
        
    
    def dfs(self, root):
        
        if root == None:
            return -1
        
        left_height = self.dfs(root.left)
        right_height = self.dfs(root.right)
        height = 1 + max(left_height, right_height)
        if height >= len(self.ans):
            self.ans.append([])
        self.ans[height].append(root.val)
        return height

Time O(n). Space O(n).

Word Break II – Python 3 (Week 12 – 17)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        return self.dfs(s, wordDict, {})
    
    def dfs(self, s, wordDict, memo):
        if s in memo:
            return memo[s]
            
        if len(s) == 0:
            return []
        partitions = []
        
        for i in range(len(s)):
            prefix = s[:i]
            if prefix not in wordDict:
                continue
            
            sub_partitions = self.dfs(s[i:], wordDict, memo)
            for partition in sub_partitions:
                partitions.append(prefix + " " + partition)
                
        if s in wordDict:
            partitions.append(s)
            
        memo[s] = partitions
        return partitions

Time O(mn). Space O(mn).

Binary Tree Upside Down – Python 3 (Week 12 – 16)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: new root
    """
    def upsideDownBinaryTree(self, root):
        # write your code here
        
        if root == None:
            return None
        return self.dfs(root)
        
        
    def dfs(self, cur):
        if cur.left == None:
            return cur
        newroot = self.dfs(cur.left)
        cur.left.right = cur
        cur.left.left = cur.right
        cur.left = None
        cur.right = None
        return newroot

Time O(h). Space O(h).

Inorder Successor in BST – Python 3 (Week 12 – 15)

class Solution:
“””
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
“””
def inorderSuccessor(self, root, p):
# write your code here
if root == None or p == None:
return None
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)
else:
leftAns = self.inorderSuccessor(root.left, p)
return root if leftAns == None else leftAns

Time O(h). Space O(h).

Sliding Puzzle II – Python 3 (Week 12 – 14)

Solution I BFS

class Solution:
    """
    @param init_state: the initial state of chessboard
    @param final_state: the final state of chessboard
    @return: return an integer, denote the number of minimum moving
    """
    def minMoveStep(self, init_state, final_state):
        # # write your code here
        st, ed = "", ""
        for i in range(3):
            for j in range(3):
                st += str(init_state[i][j])
                ed += str(final_state[i][j])
        step = 0
        fx = [0,0,1,-1]
        fy = [1,-1,0,0]
        q = collections.deque()
        v = set()
        q.append(st)
        v.add(st)
        step = 0
        while q:
            step += 1
            size = len(q)
            print(step)
            for i in range(size):
                now = q.popleft()
                index0 = now.find('0')
                x0, y0 = index0 // 3, index0 % 3
                print(x0)
                print(y0)
                for j in range(4):
                    nx, ny = x0 + fx[j], y0 + fy[j]
                    if nx < 0 or nx >= 3 or ny < 0 or ny >= 3:
                        continue
                    indexchange = nx * 3 + ny
                    a, b = max(index0, indexchange), min(index0, indexchange)
                    current = now[0:b] + now[a] + now[b + 1:a] + now[b] + now[a + 1:]
                    if current not in v:
                        if current == ed:
                            return step
                        v.add(current)
                        q.append(current)
            
        return -1

Time O(1). Space O(1).

Open the Lock – Python 3 (Week 12 – 13)

 class Solution:
    """
    @param deadends: the list of deadends
    @param target: the value of the wheels that will unlock the lock
    @return: the minimum total number of turns 
    """
    def openLock(self, deadends, target):
        # Write your code here

        dead = set(deadends)
        if '0000' in dead:
            return -1
        neighbors = set(self.adjacent(target))
        if neighbors & dead == neighbors: return -1
        visited = set()
        queue = collections.deque(['0000'])
        step = 0
        while queue:
            step += 1
            for _ in range(len(queue)):
                now = queue.popleft()
                if now == target: return step - 1
                visited.add(now)
                for n in self.adjacent(now):
                    if n in dead or n in visited: continue
                    queue.append(n)
                    visited.add(n)
        return -1
    
    def adjacent(self, now):
        res = []
        for i in range(4):
            left, mid, right = now[:i], int(now[i]), now[i + 1:]
            for m in [(mid + 1) % 10, (mid - 1) % 10]: res.append(left + str(m) + right)
        return res

Time O(n). Space O(n).

Zombie in Matrix – Python 3 (Week 12 – 12)

  class Solution:
    """
    @param grid: a 2D integer grid
    @return: an integer
    """
    def zombie(self, grid):
        # write your code here
        
        if not grid or len(grid) == 0 or len(grid[0]) == 0:
            return 0
        
        ans = 0
        
        n, m = len(grid), len(grid[0])
        
        import queue
        qx = collections.deque()
        qy = collections.deque()
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    qx.append(i)
                    qy.append(j)
                    
        while qx:
            ans += 1
            size = len(qx)
            for i in range (size):
                cx = qx.popleft()
                cy = qy.popleft()
                print(cx)
                print(cy)
                for j in range(4):
                    nx = cx + dx[j]
                    ny = cy + dy[j]
                    if nx >= 0 and nx < n and ny >= 0 and ny < m and grid[nx][ny] == 0:
                        qx.append(nx)
                        qy.append(ny)
                        grid[nx][ny] = 1
                    
           
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    return -1
        
        return ans - 1

Time O(nm). Space O(mn).

Walls and Gates – Python 3 (Week 12 – 11)

    class Solution:
    """
    @param rooms: m x n 2D grid
    @return: nothing
    """
    def wallsAndGates(self, rooms):
        # write your code here
        
        if not rooms or len(rooms) == 0 or len(rooms[0]) == 0:
            return
        
        m, n = len(rooms[0]), len(rooms)
        import queue
        qx = queue.Queue()
        qy = queue.Queue()
        
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        for i in range(n):
            for j in range(m):
                if rooms[i][j] == 0:
                    qx.put(i)
                    qy.put(j)
        
        
        while not qx.empty():
            cx = qx.get()
            cy = qy.get()
            
            for i in range(4):
                nx = cx +dx[i]
                ny = cy +dy[i]
                if nx >= 0 and nx < n and ny >= 0 and ny < m and rooms[nx][ny] == 2**31 - 1:
                    qx.put(nx)
                    qy.put(ny)
                    rooms[nx][ny] = rooms[cx][cy] + 1

Time O(nm). Space O(nm).

Surrounded Regions – Python 3 (Week 12 – 10)

Solution 1 BFS

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not board or len(board) == 0 or len(board[0]) == 0:
                return
            
        n = len(board)
        m = len(board[0])
        
        
        
        for i in range(n):
            self.bfs(board, i, 0)
            self.bfs(board, i, m - 1)
            
        for j in range(m):
            self.bfs(board, 0, j)
            self.bfs(board, n - 1, j) 
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'W':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'  
        
        
    def bfs(self, board, x, y):
        if board[x][y] != 'O':
            return
        
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        qx = []
        qy = []
        qx.append(x)
        qy.append(y)
        
        board[x][y] = 'W'
        
        while qx:
            cx = qx.pop()
            cy = qy.pop()
            
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                if nx >= 0 and nx < len(board) and ny >= 0 and ny < len(board[0]) and board[nx][ny] == 'O':
                    board[nx][ny] = 'W'
                    qx.append(nx)
                    qy.append(ny)

Time O(n * m). Space O(n * m).

Solution 2 BFS

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not any(board):
            return

        n, m = len(board), len(board[0])
        q = [ij for k in range(max(n,m)) for ij in ((0, k), (n-1, k), (k, 0), (k, m-1))]
        while q:
            i, j = q.pop()
            if 0 <= i < n and 0 <= j < m and board[i][j] == 'O':
                board[i][j] = 'W'
                q += (i, j-1), (i, j+1), (i-1, j), (i+1, j)

        board[:] = [['XO'[c == 'W'] for c in row] for row in board]