23.04.28 Today’s Leetcode

839. Similar String Groups (hard)

Brute Force Approach

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def diff(a, b):
            if len(a) != len(b):
                return -1
            count = 0
            for i in range(len(a)):
                if a[i] != b[i]:
                    count += 1
            return count
    
        def check(tar):
            res = set()
            for key in d.keys():
                temp = diff(tar, key)
                if temp == 2 or temp == 0:
                    res.add(d[key])
            return res

        group_id = 1
        res = 0
        d = {}
        for t in strs:
            group = check(t)
            if len(group) == 0:
                d[t] = group_id
                group_id += 1
                res += 1
            else:
                d[t] = group_id
                for key in d.keys():
                    if d[key] in group:
                        d[key] = group_id
                group_id += 1
                res -= len(group)
                res += 1
                
        
        # print(d)
        
        return res 

Union and Find Approach

class DSU:
    def __init__(self, l):
        self.memo = [i for i in range(l)]
    
    def find(self, x):
        if self.memo[x] != x:
            self.memo[x] = self.find(self.memo[x])
        return self.memo[x]

    def union(self, x, y):
        x_r = self.find(x)
        y_r = self.find(y)

        if x_r != y_r:
            self.memo[x_r] = y_r




class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def helper(s1, s2):
            if s1 == s2:
                return True
            ct = 0
            for i, j in zip(s1, s2):
                if i != j:
                    if ct == 2:
                        return False
                    ct += 1
            
            return True
        
        dsu = DSU(len(strs))
        for i in range(len(strs)):
            for j in range(i+1, len(strs)):
                if helper(strs[i], strs[j]):
                    dsu.union(i, j)
        
        return len(set([dsu.find(i) for i in range(len(strs))]))

840. Magic Squares In Grid (medium)

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def checkDistinct(x, y):
            d = set()
            for i in range(x, x + 3):
                for j in range(y, y + 3):

                    if grid[i][j] in d:
                        return False
                    else:
                        d.add(grid[i][j])
            return d == set([1, 2, 3, 4, 5, 6, 7, 8, 9])

        def checkRow(x, y):
            a = sum(grid[x][y:y + 3])
            b = sum(grid[x + 1][y:y + 3])
            c = sum(grid[x + 2][y:y + 3])
            return a if (a == b and b == c) else -1

        def checkCol(x, y):
            a = grid[x][y] + grid[x + 1][y] + grid[x + 2][y]
            b = grid[x][y + 1] + grid[x + 1][y + 1] + grid[x + 2][y + 1]
            c = grid[x][y + 2] + grid[x + 1][y + 2] + grid[x + 2][y + 2]
            return a if (a == b and b == c) else -1

        def checkDiag(x, y):
            a = grid[x][y] + grid[x + 1][y + 1] + grid[x + 2][y + 2]
            b = grid[x + 2][y] + grid[x + 1][y + 1] + grid[x][y + 2]
            return a if (a == b) else -1

        def isMagic(x, y):
            if x < 0 or x + 3 > m or y < 0 or y + 3 > n:
                return False
            if not checkDistinct(x, y):
                return False

            row, col = checkRow(x, y), checkCol(x, y)
            diag = checkDiag(x, y)
            # print(row, col, diag)
            return row == col and col == diag and diag > 0

        count = 0
        for i in range(m - 2):
            for j in range(n - 2):
                if isMagic(i, j):
                    count += 1
        return count
            

841. Keys and Rooms (medium)

DFS Approach

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        def dfs(cur):
            if visited[cur]:
                return
            visited[cur] = True
            for room in rooms[cur]:
                dfs(room)

        dfs(0)
        # print(visited)
        return visited == [True] * n