C++ Non-recursive Non-DP solution with "unordered_set", 3ms


  • 1
    A

    Neither particularly good, nor particularly bad.
    I also tried DP, but somehow it was slower than this. I could only get 6ms at best with DP.
    (UPDATE: Finally I figured out why my DP was slower, because I employed damned "vector<bool>". Changing it to "vector<uint>" immediately made my DP 0ms. But "unordered_set" isn't that bad either.)

    101 / 101 test cases passed.
    Status: Accepted
    Runtime: 3 ms

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            uint e1 = s1.size(), e2 = s2.size(), e3 = s3.size();
            if (e1 + e2 != e3) return false;
            unordered_set<unsigned long long> m, n;
            m.insert(0);
            for (uint j = 0; j < e3; j++) {
                for (auto& i : m) {
                    uint u1 = i, u2 = i>>32;
                    if (s3[j] != s1[u1] && s3[j] != s2[u2]) {
                        continue;
                    }
                    if (s3[j] == s1[u1]) {
                        n.insert(i+1);
                    }
                    if (s3[j] == s2[u2]) {
                        n.insert(i+(1ll<<32));
                    }
                }
                if (n.empty()) return false;
                m.clear();
                m.swap(n);
            }
            return true;
        }
    };
    

    Canonical DP solution with space optimization for reference.

    101 / 101 test cases passed.
    Status: Accepted
    Runtime: 0 ms

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            uint e1 = s1.size(), e2 = s2.size(), e3 = s3.size();
            if (e1 + e2 != e3) return false;
            if (e1 < e2) { swap(s1, s2), swap(e1, e2); }
            vector<uint> dp(e2+1);
            for (uint i = 0; i <= e1; i++) {
                for (uint j = 0; j <= e2; j++) {
                    dp[j] = (i > 0 && dp[j] && s3[i+j-1] == s1[i-1]) || (j > 0 && dp[j-1] && s3[i+j-1] == s2[j-1]) || (!i && !j);
                }
            }
            return dp[e2];
        }
    };
    

  • 0
    H

    Very clever solutions! The first one is based on BFS, Maybe using pair<int,int> instead of unsigned long long could be more readable.

    The space optimization for the DP solution is quite clever, since updating one row "table[i][:]" just requires the information of the previous row "table[i-1][:]".


  • 0
    A

    @haixiao990 If you use non-standard data type like pair, you have to provide the hash function and equal function yourself, which is a hassle.


Log in to reply
 

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