C++ easy-solution with unordered_map

• 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());
}
};
``````

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