solved 'Interleaving String' on LeetCode (6 submissions, fxxk!) http://oj.leetcode.com/problems/interleaving-string/

interleaving_string.cpp

/*
   1. first tried backtracking, TLE
   2. 2-dimension DP, accepted. state transition is easy to derive
 */
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        m = s1.size();
        n = s2.size();
        if (s3.size() != m+n) return 0;
        dp = new int*[m+1];
        for (int i=0; i<=m; ++i) {
            dp[i] = new int[n+1];
            for (int j=0; j<=n; ++j) dp[i][j] = 1;
        } // init over

        // calculate first column and first row
        for (int i=1, same=1; i<=m; ++i) {
            if (same==0) dp[i][0] = 0;
            else {
                same = (int)(s1[i-1] == s3[i-1]);
                dp[i][0] = same;
            }
        }
        for (int i=1, same=1; i<=n; ++i) {
            if (same==0) dp[0][i] = 0;
            else {
                same = (int)(s2[i-1] == s3[i-1]);
                dp[0][i] = same;
            }
        }

        // begin iteration
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                dp[i][j] = (dp[i-1][j] == 1 && s1[i-1] == s3[i+j-1]) ||
                           (dp[i][j-1] == 1 && s2[j-1] == s3[i+j-1]);   
            }
        }
        bool res = (bool)dp[m][n];
        clear_dp();
        return res;
    }
private:
    int **dp;
    int m,n;
    void clear_dp() {
        for (int i=0; i<=m; ++i) {
            delete[] dp[i];
        }
    delete[] dp;
    }
};