23.05.18 Today’s Leetcode

1790. Check if One String Swap Can Make Strings Equal (easy)

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        res = False
        if s1 == s2:
            return True
        n = len(s1)
        diff = []
        for i in range(n):
            if s1[i] != s2[i]:
                diff.append(i)
        if len(diff) != 2:
            return False
        return s1[diff[0]] == s2[diff[1]] and s2[diff[0]] == s1[diff[1]]
   

1791. Find Center of Star Graph (easy)

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        n = len(edges)
        connected = [0] * (n + 2)
        for u, v in edges:
            connected[u] += 1
            connected[v] += 1
        
        # print(connected)

        for i, v in enumerate(connected):
            if v == n:
                return i
        return -1

1557. Minimum Number of Vertices to Reach All Nodes

Union-Find Approach failed at 9/63

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        xset, yset = self.find(x), self.find(y)
        if xset != yset:
            if self.rank[xset] < self.rank[yset]:
                self.parent[xset] = yset
            elif self.rank[xset] > self.rank[yset]:
                self.parent[yset] = xset
            else:
                self.parent[xset] = yset
                self.rank[yset] += 1
            return True
        return False


class Solution:

    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        p = DSU(n)
        edges.sort(key= lambda x: x[0])

        for u, v in edges:
            a, b = p.find(u), p.find(v)
            print(a, b)
            if a < b:
                p.union(u, v)
        
        print(p.parent)
        visited = set()
        res = []
        for i in range(n):
            f = p.find(i)
            if f not in visited:
                res.append(i)
            visited.add(f)

        return res

indegree

class Solution:
    def findSmallestSetOfVertices(self, n, edges):
        indegree = [0] * n
        for edge in edges:
            indegree[edge[1]] += 1

        ans = []
        for i in range(n):
            if indegree[i] == 0:
                ans.append(i)

        return ans