Algorithms & Data Structures : Union Find Problems

Problem

LeetCode 200. Number of Islands

LeetCode : 737. Sentence Similarity II
[Union-Find][String][Hash Table][Depth-First Search]

LeetCode 200. Number of Islands

這一題用 BFS 或是 DFS 可以很簡單的解出來，這邊試著用這題練習簡易的 Union Find。

一開始，只要遇到 1 就將 counter 加上 1 。之後只要 union 成功，counter 就 減 1 ，最後 counter 就是 island 個數。

class Solution {
private:
    int X[4] = {0, 0, 1, -1};
    int Y[4] = {1, -1, 0, 0};
    
    int counter = 0;
    vector<int> parent;
    int find_root(int x) {
        if(parent[x] != x) {
            parent[x] = find_root(parent[x]);
            return parent[x];
        }
        return x;
    }
    void union2set(int x, int y) {
        x = find_root(x);
        y = find_root(y);
        if(x != y) {
            counter--;
            parent[x] = y;
        }
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        parent = vector<int>(grid.size() * grid[0].size());
        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                if('1' == grid[i][j]) {
                    counter++;
                    parent[i * grid[0].size() + j] = i * grid[0].size() + j;
                }
            }
        }

        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                if('1' == grid[i][j]) {
                    for(int q = 0;q < 4;q++) {
                        int newx = i + X[q];
                        int newy = j + Y[q];
                        
                        if(newx >= 0 && newx < grid.size() &&
                           newy >= 0 && newy < grid[0].size() &&
                           '1' == grid[newx][newy]) {
                            union2set(i * grid[0].size() + j, newx * grid[0].size() + newy);
                        }
                    }
                }
            }
        }
        
        return counter;
    }
};

LeetCode : 737. Sentence Similarity II

// union-find, 先把 string 轉成 int ， 
// 一個個 word 去判斷兩個 sentence 的 word 是否為同一個
int findParent(int x, vector<int> &p)
{
    if(x == p[x]) {
        return x;
    }
    p[x] = findParent(p[x], p);
    return p[x];
}
void union2sets(int x, int y, vector<int> &p) 
{
    x = findParent(x, p);
    y = findParent(y, p);
    if(x != y) {
        p[x] = y;
    }
}
class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        
        if(sentence1.size() != sentence2.size()) {
            return false;
        }
        
        unordered_map<string, int> s2i;
        
        int index = 0;
        for(int i = 0;i < similarPairs.size();i++) {
            if(s2i.find(similarPairs[i][0]) == s2i.end()) {
                s2i[similarPairs[i][0]] = index;
                index++;
            }
            if(s2i.find(similarPairs[i][1]) == s2i.end()) {
                s2i[similarPairs[i][1]] = index;
                index++;
            }
        }
        
        vector<int> parent = vector<int>(index, -1);
        for(int i = 0;i < parent.size();i++) {
            parent[i] = i;
        }
        
        for(int i = 0;i < similarPairs.size();i++) {
            int x = s2i[similarPairs[i][0]];
            int y = s2i[similarPairs[i][1]];
            union2sets(x, y, parent);
        }
        
        for(int i = 0;i < sentence1.size();i++) {
            int x, y;
            if(s2i.find(sentence1[i]) == s2i.end()) {
                x = -1;
            } else {
                x = s2i[sentence1[i]];
            }
            if(s2i.find(sentence2[i]) == s2i.end()) {
                y = -1;
            } else {
                y = s2i[sentence2[i]];
            }
            
            if(-1 == x && -1 == y) {
                if(sentence1[i] != sentence2[i]) {
                    return false;
                }
            } else if(-1 == x && -1 != y) {
                return false;
            } else if(-1 != x && -1 == y) {
                return false;
            } else {
                if(findParent(x, parent) != findParent(y, parent)) {
                    return false;
                }   
            }
        } 
        
        return true;
    }
};