23.05.21 Today’s Leetcode

934. Shortest Bridge (medium)

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q, head = [], -1
        dis = []
        visited = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q = [[i, j]]
                    visited[i][j] = True
                    dis.append(0)
                    break
            if len(q) > 0:
                break
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while head < len(q) - 1:
            head += 1
            x, y = q[head][0], q[head][1]
            for d in dirs:
                xx, yy = x + d[0], y + d[1]
                if xx < 0 or xx >= n or yy < 0 or yy >= n:
                    continue
                if visited[xx][yy] or grid[xx][yy] == 0:
                    continue
                q.append([xx, yy])
                visited[xx][yy] = True
                dis.append(0)
        head = -1
        while head < len(q) - 1:
            head += 1
            x, y = q[head][0], q[head][1]
            for d in dirs:
                xx, yy = x + d[0], y + d[1]
                if xx < 0 or xx >= n or yy < 0 or yy >= n or visited[xx][yy]:
                    continue
                q.append([xx, yy])
                visited[xx][yy] = True
                dis.append(dis[head] + 1)
                if grid[xx][yy] == 1:
                    return dis[-1] - 1
        return 0

935. Knight Dialer (medium)

class Solution:
    def knightDialer(self, n: int) -> int:
        tree = [
            [4, 6], 
            [8, 6], 
            [7, 9], 
            [4, 8], 
            [3, 9, 0], 
            [], 
            [1, 7, 0], 
            [2, 6],
            [1, 3],
            [4, 2],
        ]

        dp = {}

        @functools.lru_cache(None)
        def dfs(cur, count):
            if count <= 1:
                return count
            res = 0
            for num in tree[cur]:
                res += dfs(num, count - 1)
            # dp[cur][count] = res
            return res

        res = 0
        for i in range(10):
            res += dfs(i, n)

        return res % (10**9 + 7)
            

Memoization Approach

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [1] * 10
        for _ in range(n - 1):
            new_dp = [0] * 10
            new_dp[0] = (dp[4] + dp[6]) % MOD
            new_dp[7] = (dp[2] + dp[6]) % MOD
            new_dp[8] = (dp[1] + dp[3]) % MOD
            new_dp[4] = (dp[3] + dp[9] + dp[0]) % MOD
            new_dp[5] = 0
            new_dp[1] = (dp[6] + dp[8]) % MOD
            new_dp[2] = (dp[7] + dp[9]) % MOD
            new_dp[3] = new_dp[1]
            new_dp[6] = new_dp[4]
            new_dp[9] = new_dp[7]
            dp = new_dp
        return sum(dp) % MOD

936. Stamping The Sequence (hard)

Failed

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        n = len(stamp)
        m = len(target)
        visited = [0] * m
        res = []
        left, right = math.inf, -math.inf
        for i in range(m - n + 1):
            if stamp == target[i:i + n]:
                left = min(left, i)
                right = max(right, i + n)
                for j in range(i, i + n):
                    visited[j] = 1
                res.append(i)

        def extend():
            nonlocal left, right
            for j in range(max(0, left - n), left):
                # print(target[j:left])
                if target[j:left] in stamp:
                    left = j
                    res.append(j)
                    break
            for j in range(min(m, right + n + 1), right, -1):
                # print(target[right:j])
                if target[right:j] in stamp:
                    right = j
                    res.append(j - n)
                    break
                
        count = len(res)
        while left > 0 or right < m:
            # print(res, left, right)
            extend()
            count += 1
            if count > 10 * len(target):
                return []

        return res[::-1]

Greedy Approach

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        N,M = len(target),len(stamp)
        move = 0
        maxmove = 10*N
        ans = []
        def check(string):
            for i in range(M):
                if string[i] == stamp[i] or string[i] == '?':
                    continue
                else:
                    return False
            return True
        
        while move < maxmove:
            premove = move
            for i in range(N-M+1):
                if check(target[i:i+M]):
                    move += 1
                    ans.append(i)
                    target = target[:i] + "?"*M + target[i+M:]
                    if target == "?"*N : return ans[::-1]
            if premove == move:return []
        return []

939. Minimum Area Rectangle (medium)

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        res = math.inf
        d = set()
        for point in points:
            d.add(tuple(point))
        
        def help(point):
            nonlocal res
            x, y = point
            for p in points:
                a, b = p
                if x == a or y == b: continue
                if (x, b) in d and (a, y) in d:
                    res = min(res, abs((x - a) * (y - b)))

        for point in points:
            help(point)

        return res if res != math.inf else 0