Leetcode 1257: Smallest Common Region

https://leetcode.com/contest/biweekly-contest-13/problems/smallest-common-region/

Notes:

This is a good question, which is equivalent to find the lowest common ancestor (LCA).

Since this is not a tree structure, we can build the relationship from children to parents, which then is much easier to find the common ancestor.

One way is that we can use BFS: start with the two strings, then gradually search the upper layers layer by layer. The first found common string is the LCA.

One corner case is that: one of the string may reach the root first. In this case, we need to make sure, the search can continue until find the LCA.

See the code below:

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        unordered_map<string, string> ps;//parents
        unordered_map<string, bool> visit;
        for(auto &a : regions) {
            for(int i=1; i<a.size(); ++i) ps[a[i]] = a[0];
        }
        queue<string> q;
        q.push(region1);
        visit[region1] = true;
        q.push(region2);
        visit[region2] = true;
        while(q.size()) {
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                if(ps[t] != "") {//corner case: when one of them reach the root
                    string a = ps[t];
                    if(visit.count(a)) return a;
                    q.push(a);
                    visit[a] = true;
                }
            }
        }
        return "";//if there is no LCA
    }
};