2.5 Union Find/ Trie Tree

并查集：集合查询合并 支持O(1)find/O(1)union

Union Find

并查集的操作

1. 查询是否在同一个集合 Find (递归? 非递归?)：O(1) find

1. 合并集合 Union： O(1) union

严谨地说：log*n

templete

class UnionFind:
    self.father = []
    def self.find(x):
        if self.father[x] == x:
            return x
        self.father[x] = find(self.father[x])
        return self.father[x]
        
    def self.union(a,b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            father[root_a] = root_b
    
    

application(graph)

Connecting Graph问题的总结

• 并查集原生操作:

•查询两个元素是否在同一个集合内 •合并两个元素所在的集合

• 并查集的派生操作:

•查询某个元素所在集合的元素个数 •查询当前集合的个数

Number of Connected Components in an Undirected Graph

'''
union find:
time:O(n)
space:O(n)
'''
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:     
        self.count = n
        self.father = [i for i in range(n)]
        
        def find(a):
            if self.father[a] == a:
                return a
            self.father[a] = find(self.father[a])
            return self.father[a]
        
        def connect(i,j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                self.father[root_i] = root_j
                self.count -= 1
                
        for i,j in edges:
            connect(i,j)
            # print(i,j)
        return self.count
'''
bfs:
time:O(n)
space:O(n)
'''
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:   
        graph = {i:set() for i in range(n)}
        seen = set()
        count = 0
        for i,j in edges:
            graph[i].add(j)
            graph[j].add(i)
        def bfs(i):
            queue = [i]
            while queue:
                node = queue.pop(0)
                for j in graph[node]:
                    if j not in seen:
                        seen.add(j)
                        queue.append(j)
        for i in range(n):
            if i not in seen:
                bfs(i)
                count += 1
        return count

'''
dfs:
time:O(n)
space:O(n)
'''
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:   
        graph = {i:set() for i in range(n)}
        seen = set()
        count = 0
        for i,j in edges:
            graph[i].add(j)
            graph[j].add(i)
            
        def dfs(i):
            if i in seen:
                return
            seen.add(i)
            for j in graph[i]:
                dfs(j)

        for i in range(n):
            if i not in seen:
                dfs(i)
                count += 1
        return count

Number of Islands

'''
bfs:
seen = set()
for position(i,j):
    if value = 1 and not in seen:
        count += 1
        bfs(i,j)
'''
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        row = len(grid)
        col = len(grid[0])
        def bfs(i,j):
            queue = [(i,j)]
            while queue:
                x, y = queue.pop(0)
                for dx, dy in [(0,1),(1,0),(-1,0),(0,-1)]:
                    ni = x+dx
                    nj = y+dy
                    if 0<=ni<row and 0<=nj<col:
                        if grid[ni][nj] == '1':
                            grid[ni][nj] = '#'
                            queue.append((ni,nj))
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    grid[i][j] == '#'
                    bfs(i,j)
                    count += 1
        return count
        
'''
dfs
time: O(mn)
space:O(mn)
'''
class Solution:
        
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j-1)
        
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        count = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    self.dfs(grid, i,j)
                    count += 1
        return count
    
'''
union find
count = 0
father = []
union(i,j)
find(i)
time:O(mn)
space:O(mn)
'''
class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.father = [-1] * (m*n)
        self.rank = [0] * (m*n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.father[i*n + j] = i*n + j
                    self.count += 1

        
    def find(self, i):
        if self.father[i] == i:
            return i
        self.father[i] = self.find(self.father[i])
        return self.father[i]
    
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.count -= 1
            self.father[root_a] = root_b
            
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def is_island(i,j):
            if i<0 or j<0 or i>=len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
                return False
            return True
        
        uf = UnionFind(grid)
        directions = [(0,1), (0,-1), (-1,0), (1,0)]
        col = len(grid[0])
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    for nei in directions:
                        ni,nj = i+nei[0], j+nei[1]
                        if is_island(ni,nj):
                            uf.union(i*col+j, ni*col+nj)
        return uf.count
                        

Number of Islands II

'''
union find:
father = [-1]*mn
count = 0
for each postion, 
    count += 1
    check 4 nei: if 1, connect
    add the count
time :O(mn + k): init uf = mn
space: O(mn)
'''
class UnionFind:
    def __init__(self, m, n):
        self.father = [-1]*m*n
        self.count = 0
    
    def find(self, x):
        if self.father[x] == x:
            return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]
    
    def connect(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.count -= 1
            self.father[root_a] = root_b
            
class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        def is_island(x,y):
            if x<0 or x>=m or y<0 or y>= n or uf.father[x*n+y] == -1:
                return False
            return True
        
        uf = UnionFind(m,n)
        res = []
        for new in positions:
            if uf.father[new[0]*n+new[1]] == -1:
                uf.father[new[0]*n+new[1]] = new[0]*n+new[1]
                uf.count += 1
            for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                nx, ny = new[0]+dx, new[1]+dy
                if is_island(nx,ny):
                    # print(nx, ny)
                    uf.connect(new[0]*n+new[1], nx*n+ny)
            res.append(int(uf.count))
        return res
            

Number of Distinct Islands

'''
dfs
shapes = set(unfrozenset((0,0),(0,-1))...)
return len(shapes)
time :O(mn)
space: O(mn)
'''
class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        shapes = set()
        m,n = len(grid), len(grid[0])
        
        def dfs(i,j, i0, j0, shape):
            if i < 0 or j <0 or i>=m or j >= n or grid[i][j] != 1:
                return
            grid[i][j] = 0
            shape.add((i-i0,j-j0))
            dfs(i+1, j, i0, j0, shape)
            dfs(i-1, j, i0, j0, shape)
            dfs(i, j+1, i0, j0, shape)
            dfs(i, j-1, i0, j0, shape)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    shape = set()
                    dfs(i,j, i, j, shape)
                    # print(shape)
                    if shape:
                        shapes.add(frozenset(shape))
        return len(shapes)

* Graph Valid Tree

* Surrounded Regions

Trie Tree

1.考点：

Trie直接实现 利用Trie树前缀特性解题 矩阵类字符串一个一个字符深度遍历的问题

2. Hash vs Trie

时间复杂度Hash O(1) 是对于一个字符串

1.time complexity: same

2.space: trie < hash e.g.[a, aa, aaa, aaaa]

3.properties: hash is easier

Implement Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                child = TrieNode()
                cur.children[c] = child
            cur = cur.children[c]
        cur.isWord = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.isWord
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

2.利用Trie树前缀特性解题:

Design Add and Search Words Data Structure

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        cur = self.root 
        for c in word:
            if c not in cur.children:
                child = TrieNode()
                cur.children[c] = child
            cur = cur.children[c]
        cur.isWord = True
    
    def find(self, word, index, node):
        if index == len(word):
            return node.isWord
        c = word[index]
        if c == '.':
            for child in node.children:
                if self.find(word, index+1, node.children[child]):
                    return True
            return False
        else:
            if c not in node.children.keys():
                return False
            return self.find(word, index+1, node.children[c])
        
            
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        return self.find(word, 0, self.root)
        


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

3. 矩阵类字符串一个一个字符深度遍历的问题(DFS+TRIE)

•DFS 树 和 Trie树同时遍历

Word Search II

'''
dfs+trie tree
build a trie for words
iterate the board,
    using dfs to check if the path is the trie
'''
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.word = ''
class Trie:
    def __init__(self): 
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children.keys():
                new = TrieNode()
                node.children[c] = new
            node = node.children[c] 
        node.isWord = True
    
    
class Solution:
    def dfs(self, board, i, j, node, path, res):
        if node.isWord:
            res.append(path)
            node.isWord = False
            return 
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return 
        tem = board[i][j]
        node = node.children.get(board[i][j])
        if not node:
            return
        board[i][j] = '#'
        self.dfs(board, i+1, j, node, path+tem, res)
        self.dfs(board, i-1, j, node, path+tem, res)
        self.dfs(board, i, j+1, node, path+tem, res)
        self.dfs(board, i, j-1, node, path+tem, res)
        board[i][j] = tem
        
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        myTrie = Trie()
        #insert words to trie
        for word in words:
            myTrie.insert(word)
            
        #search board
        res = []
        node = myTrie.root
        m,n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                self.dfs(board, i, j, node, '', res)
        return res
                
                
                

Word Square

'''
dfs+trie
first level, check the child to get first row
for c in word:
    find prefix
'''
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.wordList = []
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children.keys():
                node.children[c] = TrieNode()
            node.wordList.append(word)
            node = node.children[c]
        node.isWord = True
        
    def findPre(self, pre):
        node = self.root
        for c in pre:
            if c not in node.children.keys():
                return None
            node = node.children[c]
        return node
    
    def findPreWords(self, pre):
        node = self.findPre(pre)
        return node.wordList
        
class Solution:
    def find(self, trie, ans, res):
        cur, last = len(ans), len(ans[0])
        if cur == last:
            res.append(list(ans))
            # print(ans)
            return
        #check if the prefix is available
        for i in range(cur, last):
            prefix = ''.join(ans[row][i] for row in range(cur))
            if not trie.findPre(prefix):
                return 
        #
        pre = ''.join(ans[row][cur] for row in range(cur))
        # print(pre)
        for word in trie.findPreWords(pre):
            ans.append(word)
            # print(ans)
            self.find(trie, ans, res)
            ans.pop()
                
            
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        trie = Trie()
        for w in words:
            trie.insert(w)
        res = []
        node = trie.root
        for w in words:
            self.find(trie, [w], res)
        return res