[LeetCode] Interleaving String

 

Interleaving String

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

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

方法：感觉方法很笨。可能是dp状态找的不好。

本方法：

S(i,j) = 1

if (s1[i+1] == s3[i+j+1]) S(i+1,j) = 1

if (s2[j+1] == s3[i+j+1]) S(i,j+1) = 1

如有好的方法，请告诉我啊！！

 

 

#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    bool m[100][100];
    bool isInterleave(string s1, string s2, string s3) {
        memset(m, 0, sizeof(m));
        if (s1.size() + s2.size() != s3.size()) return false;
        queue<pair<int,int> > q;
        q.push(make_pair(0,0));
        int i1, i2, t;
        while (!q.empty()) {
            i1 = q.front().first;
            i2 = q.front().second;
            q.pop();
            t = i1 + i2;
            if (t == s3.size()) return true;
            if (i1 < s1.size() && s3[t] == s1[i1]) {
                if (!m[i1+1][i2]){
                    m[i1+1][i2] = true;
                    q.push(make_pair(i1+1, i2));
                }
            }
            if (i2 < s2.size() && s3[t] == s2[i2]) {
                if (!m[i1][i2+1]) {
                    m[i1][i2+1] = true;
                    q.push(make_pair(i1, i2+1));
                }
            }
        }
        return false;
    }
};

 

做完后，发现之前做过。

dp[i][j] = true, 表示s1[0~i]和s2[0~j]可以搞成s3[i+j]

dp[i][j] = 

               1. true: dp[i-1][j] = true && s1[i] == s3[i+j]

                    2. true: dp[i][j-1] = true && s2[j] == s3[i+j]

               3. false: else

 

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.size(), l2 = s2.size(), l3 = s3.size();
        if (l3 != l1 + l2) return false;
        
        bool dp[l1+1][l2+1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = true;
        for (int len = 1; len <= l3; len++) {
            for (int i = 0; i <= len && i <= l1; i++) {
                int j = len - i;
                if (j > l2) continue;
                dp[i][j] = false;
                if (i > 0 && dp[i-1][j] && s1[i-1] == s3[len-1]) dp[i][j] = true;
                if (j > 0 && dp[i][j-1] && s2[j-1] == s3[len-1]) dp[i][j] = true;
                
            }
        }
        return dp[l1][l2];
    }
};