97. Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + … + sn
• t = t1 + t2 + … + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + …

Note: a + b is the concatenation of strings a and b.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int s1len(s1.length()), s2len(s2.length());
        bool v[101][101]{true,};
        queue<pair<int, int>> q;
        q.push({0,0});

        while(!q.empty()) {
            auto p = q.front(); q.pop();
            if(p.first < s1len && s3[p.first + p.second] == s1[p.first] && !v[p.first + 1][p.second]) {
                v[p.first + 1][p.second] = true;
                q.push({p.first + 1, p.second});
            }
            if(p.second < s2len && s3[p.first + p.second] == s2[p.second] && !v[p.first][p.second + 1]) {
                v[p.first][p.second + 1] = true;
                q.push({p.first, p.second + 1});
            }
        }

        return s1len + s2len == s3.length() && v[s1len][s2len];
    }
};