LeetCode 737 - Sentence Similarity II


http://zxi.mytechroad.com/blog/hashtable/leetcode-737-sentence-similarity-ii/
Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.
For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].
Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.
Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.
Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.
Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].
Note:
  • The length of words1 and words2 will not exceed 1000.
  • The length of pairs will not exceed 2000.
  • The length of each pairs[i] will be 2.
  • The length of each words[i] and pairs[i][j] will be in the range [1, 20].
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)

X. Time complexity: O(|Pairs| * |words1|)
Space complexity: O(|Pairs|)
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        // Build the graph of pairs
        HashMap<String, Set<String>> pairMap = new HashMap<>();
        for (String[] pair : pairs) {
            // Create keys(words in [][]pairs without duplication) and empty set 
            if (!pairMap.containsKey(pair[0])) {
                pairMap.put(pair[0], new HashSet<String>());
            }
            if (!pairMap.containsKey(pair[1])) {
                pairMap.put(pair[1], new HashSet<String>());
            }
            // Add the corresponding pairs to each other
            pairMap.get(pair[0]).add(pair[1]);
            pairMap.get(pair[1]).add(pair[0]);
        }
     
        // Iterate throught each word in both input strings and do DFS search
        for (int i = 0; i < words1.length; i++) {
            // If same, then we don't need to do DFS search
            if (words1[i].equals(words2[i])) continue;
            // If they are not the same and no such strings in the pairs
            if (!pairMap.containsKey(words1[i]) || !pairMap.containsKey(words2[i])) return false;
            // Do DFS search, initialize the set to prevent revisiting. 
            if (!dfs(words1[i], words2[i], pairMap, new HashSet<>())) return false;
        }
        return true;
    }
        
    public boolean dfs(String source, String target, HashMap<String, Set<String>> pairMap, HashSet<String> visited) {
        if (pairMap.get(source).contains(target)) {
            return true;
        }
        // Mark as visited 
        visited.add(source);
        for (String next : pairMap.get(source)) {
            // DFS other connected node, except the mirrowed string 
            if (!visited.contains(next) && next.equals(target) ||
                !visited.contains(next) && dfs(next, target, pairMap, visited)) {
                return true;    
            }
        }
        // We've done dfs still can't find the target 
        return false;
    }
X. DFS
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)
C++ / DFS Optimized
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
        if (words1.size() != words2.size()) return false;
        
        g_.clear();
        ids_.clear();
        
        for (const auto& p : pairs) {
            g_[p.first].insert(p.second);
            g_[p.second].insert(p.first);
        }        
        
        int id = 0;
        
        for (const auto& p : pairs) {
            if(!ids_.count(p.first)) dfs(p.first, ++id);
            if(!ids_.count(p.second)) dfs(p.second, ++id);
        }
        
        for (int i = 0; i < words1.size(); ++i) {
            if (words1[i] == words2[i]) continue;
            auto it1 = ids_.find(words1[i]);
            auto it2 = ids_.find(words2[i]);
            if (it1 == ids_.end() || it2 == ids_.end()) return false;
            if (it1->second != it2->second) return false;
        }
        
        return true;
    }
private:
    bool dfs(const string& curr, int id) {
        ids_[curr] = id;        
        for (const auto& next : g_[curr]) {
            if (ids_.count(next)) continue;
            if (dfs(next, id)) return true;
        }
        return false;
    }
    
    unordered_map<string, int> ids_;
    unordered_map<string, unordered_set<string>> g_;


X. BFS
http://www.cnblogs.com/grandyang/p/8053934.html
这道题是之前那道Sentence Similarity的拓展，那道题说单词之间不可传递，于是乎这道题就变成可以传递了，那么难度就增加了。不过没有关系，还是用我们的经典老三样来解，BFS，DFS，和Union Find。我们先来看BFS的解法，其实这道题的本质是无向连通图的问题，那么首先要做的就是建立这个连通图的数据结构，对于每个结点来说，我们要记录所有和其相连的结点，所以我们建立每个结点和其所有相连结点集合之间的映射，比如对于这三个相似对(a, b), (b, c)，和(c, d)，我们有如下的映射关系：
a -> {b}
b -> {a, c}
c -> {b, d}
d -> {c}
那么如果我们要验证a和d是否相似，就需要用到传递关系，a只能找到b，b可以找到a，c，为了不陷入死循环，我们将访问过的结点加入一个集合visited，那么此时b只能去，c只能去d，那么说明a和d是相似的了。那么我们用for循环来比较对应位置上的两个单词，如果二者相同，那么直接跳过去比较接下来的。否则就建一个访问即可visited，建一个队列queue，然后把words1中的单词放入queue，建一个布尔型变量succ，标记是否找到，然后就是传统的BFS遍历的写法了，从队列中取元素，如果和其相连的结点中有words2中的对应单词，标记succ为true，并break掉。否则就将取出的结点加入队列queue，并且遍历其所有相连结点，将其中未访问过的结点加入队列queue继续循环

https://protegejj.gitbooks.io/algorithm-practice/content/737-sentence-similarity-ii.html
(1) 用union find的关键就是要给每个pair里的word分配一个unique id，然后用map存string到id的关系
(2) 在遍历words1和words2，如果map里面没有words1或words2当前的词或者通过find我们发现当前word1和word2不在一个集合里，return false
Union Find: 时间复杂度O(k + n), 空间复杂度O(k)
class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }

        UnionFind uf = new UnionFind(2 * pairs.length);

        Map<String, Integer> map = new HashMap<>();
        int id = 0;

        for (String[] pair : pairs) {
            for (String word : pair) {
                if (!map.containsKey(word)) {
                    map.put(word, id);
                    ++id;
                }
            }

            uf.union(map.get(pair[0]), map.get(pair[1]));
        }


        for (int i = 0; i < words1.length; i++) {
            String word1 = words1[i];
            String word2 = words2[i];

            if (word1.equals(word2)) {
                continue;
            }

            if (!map.containsKey(word1) || !map.containsKey(word2) || uf.find(map.get(word1)) != uf.find(map.get(word2))) {
                return false;
            }
        }
        return true;
    }

    class UnionFind {
        int[] sets;
        int[] size;
        int count;

        public UnionFind(int n) {
            sets = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                sets[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != sets[node]) {
                node = sets[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int node1 = find(i);
            int node2 = find(j);

            if (node1 == node2) {
                return;
            }

            if (size[node1] < size[node2]) {
                sets[node1] = node2;
                size[node2] += size[node1];
            }
            else {
                sets[node2] = node1;
                size[node1] += size[node2];
            }
            --count;
        }
    }

C++ / Union Find
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)

    bool Union(const string& word1, const string& word2) {
        const string& p1 = Find(word1, true);
        const string& p2 = Find(word2, true);
        if (p1 == p2) return false;        
        parents_[p1] = p2;
        return true;
    }
    
    const string& Find(const string& word, bool create = false) {
        if (!parents_.count(word)) {
            if (!create) return word;
            return parents_[word] = word;
        }
        
        string w = word;
        while (w != parents_[w]) {
            parents_[w] = parents_[parents_[w]];
            w = parents_[w];
        }
        
        return parents_[w];
    }
private:
    unordered_map<string, string> parents_;
};
class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
        if (words1.size() != words2.size()) return false;
        
        UnionFindSet s;
        for (const auto& pair : pairs)
            s.Union(pair.first, pair.second);
        
        for (int i = 0; i < words1.size(); ++i)
            if (s.Find(words1[i]) != s.Find(words2[i])) return false;
        
        return true;
    }
https://www.jianshu.com/p/43fe7cc6797b
https://gist.github.com/aquawj/1d8b62533b7a5d6633013cd0d5a47a43
  public boolean areSentencesSimilarTwo(String[] a, String[] b, String[][] pairs) {
    if (a.length != b.length)
      return false;
    Map<String, String> m = new HashMap<>();
    for (String[] p : pairs) {
      String parent1 = find(m, p[0]), parent2 = find(m, p[1]);
      if (!parent1.equals(parent2))
        m.put(parent1, parent2);
    }

    for (int i = 0; i < a.length; i++)
      if (!a[i].equals(b[i]) && !find(m, a[i]).equals(find(m, b[i])))
        return false;

    return true;
  }

  private String find(Map<String, String> m, String s) {
    if (!m.containsKey(s))
      m.put(s, s);
    return s.equals(m.get(s)) ? s : find(m, m.get(s));

  }
题解：用map<String, String>来实现union and find
  public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
    if (words1.length != words2.length)
      return false;
    Map<String, String> map = new HashMap<>();
    for (String[] pair : pairs) {
      String parent0 = find(pair[0], map);
      String parent1 = find(pair[1], map);
      if (!parent0.equals(parent1))
        map.put(parent0, parent1);
    }
    int n = words1.length;
    for (int i = 0; i < n; i++) {
      if (!words1[i].equals(words2[i]) && !find(words1[i], map).equals(find(words2[i], map)))
        return false;
    }
    return true;
  }

  private String find(String word, Map<String, String> map) {
    if (!map.containsKey(word))
      return word;
    String str = word;
    while (map.containsKey(str)) {
      str = map.get(str);
    }
    map.put(word, str);
    return str;

  }
X. 
DFS: 时间复杂度O(nk), 其中n为words的长度， k为pairs的长度，空间复杂度O(k)

  public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
    if (words1.length != words2.length) {
      return false;
    }
    // Build the graph of pairs
    HashMap<String, Set<String>> pairMap = new HashMap<>();
    for (String[] pair : pairs) {
      // Create keys(words in [][]pairs without duplication) and empty set
      if (!pairMap.containsKey(pair[0])) {
        pairMap.put(pair[0], new HashSet<String>());
      }
      if (!pairMap.containsKey(pair[1])) {
        pairMap.put(pair[1], new HashSet<String>());
      }
      // Add the corresponding pairs to each other
      pairMap.get(pair[0]).add(pair[1]);
      pairMap.get(pair[1]).add(pair[0]);
    }

    // Iterate throught each word in both input strings and do DFS search
    for (int i = 0; i < words1.length; i++) {
      // If same, then we don't need to do DFS search
      if (words1[i].equals(words2[i]))
        continue;
      // If they are not the same and no such strings in the pairs
      if (!pairMap.containsKey(words1[i]) || !pairMap.containsKey(words2[i]))
        return false;
      // Do DFS search, initialize the set to prevent revisiting.
      if (!dfs(words1[i], words2[i], pairMap, new HashSet<>()))
        return false;
    }
    return true;
  }

  public boolean dfs(String source, String target, HashMap<String, Set<String>> pairMap, HashSet<String> visited) {
    if (pairMap.get(source).contains(target)) {
      return true;
    }
    // Mark as visited
    visited.add(source);
    for (String next : pairMap.get(source)) {
      // DFS other connected node, except the mirrowed string
      if (!visited.contains(next) && next.equals(target)
          || !visited.contains(next) && dfs(next, target, pairMap, visited)) {
        return true;
      }
    }
    // We've done dfs still can't find the target
    return false;

  }
http://zxi.mytechroad.com/blog/hashtable/leetcode-737-sentence-similarity-ii/
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)
C++ / DFS Optimized
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
        if (words1.size() != words2.size()) return false;
        
        g_.clear();
        ids_.clear();
        
        for (const auto& p : pairs) {
            g_[p.first].insert(p.second);
            g_[p.second].insert(p.first);
        }        
        
        int id = 0;
        
        for (const auto& p : pairs) {
            if(!ids_.count(p.first)) dfs(p.first, ++id);
            if(!ids_.count(p.second)) dfs(p.second, ++id);
        }
        
        for (int i = 0; i < words1.size(); ++i) {
            if (words1[i] == words2[i]) continue;
            auto it1 = ids_.find(words1[i]);
            auto it2 = ids_.find(words2[i]);
            if (it1 == ids_.end() || it2 == ids_.end()) return false;
            if (it1->second != it2->second) return false;
        }
        
        return true;
    }
private:
    bool dfs(const string& curr, int id) {
        ids_[curr] = id;        
        for (const auto& next : g_[curr]) {
            if (ids_.count(next)) continue;
            if (dfs(next, id)) return true;
        }
        return false;
    }
    
    unordered_map<string, int> ids_;
    unordered_map<string, unordered_set<string>> g_;

    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
        if (words1.size() != words2.size()) return false;
        unordered_map<string, unordered_set<string>> m;
        for (auto pair : pairs) {
            m[pair.first].insert(pair.second);
            m[pair.second].insert(pair.first);
        }
        for (int i = 0; i < words1.size(); ++i) {
            unordered_set<string> visited;
            if (!helper(m, words1[i], words2[i], visited)) return false;
        }
        return true;
    }
    bool helper(unordered_map<string, unordered_set<string>>& m, string& cur, string& target, unordered_set<string>& visited) {
        if (cur == target) return true;
        visited.insert(cur);
        for (string word : m[cur]) {
            if (!visited.count(word) && helper(m, word, target, visited)) return true;
        }
        return false;
    }

X. 
at
Labels: , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Print all sequences of given length | GeeksforGeeks
    Print all sequences of given length | GeeksforGeeks Given two integers k and n, write a function that prints all the sequences of length k...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 860 - Lemonade Change
    https://leetcode.com/problems/lemonade-change/description/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a ...
  • Uber Interview
    优步面经 Email domain address typo, need to figure out and return correct domain name. e.g. yhaoo–> yahoo, giaml –> gmail, hmailot–> ...