C++ easy-solution with unordered_map


  • 0
    L

    For string a = "ab", b="cd", s="acbd";
    The idea is to use the hash map to record the all possible (i, j) pairs so that we can use a(0, i) and b(0, j) to form s(0, i + j).

    Actually, it will be easy to understand if we use unordered_set<pair<int, int>> to record such (i, j) pairs. But it requires to implement the hash function for pair to the key of a set. Therefore, instead we use unordered_map<int, int> to mimic the set. The key will be i index, and value will be j index.

    class Solution {
    public:
        bool isInterleave(string a, string b, string s) {
            if(a.empty() && b.empty() && s.empty()) return true;
            if(s.size() != a.size() + b.size()) return false;
    
            unordered_map<int, int> mp, temp;
            mp[-1] = -1;
            int k = 0;
            for(; k < s.size(); ++ k){
                temp.clear();
                for(auto & m: mp){
                    int i = m.first, j = m.second;
                    if(a[i + 1] == s[k]) temp[i + 1] = j;
                    if(b[j + 1] == s[k]) temp[i] = j + 1;
                }
                mp.swap(temp);
                if(mp.empty()) break;
            }
            return (k == s.size() && !mp.empty()); 
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.