Interleaving String

题目：

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example: For s1 = "aabcc", s2 = "dbbca"

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

分析：

这道题目的有趣之处在于初始化的过程，实际上是尽可能多的去初始化了s1和s2中的起始部位中的连续部分。至于为什么这么初始化，我也不知道...

解法：

class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        int m = s1.size();
        int n = s2.size();
        if (m + n != s3.size() ) {
            return false;
        }
        if (m == 0) {
            return s2 == s3;
        }
        if (n == 0) {
            return s1 == s3;
        }

        vector<vector<bool> > f(m + 1, vector<bool>(n + 1, false) );
        f[0][0] == true;
        for (int i = 1; i <= m; i++) {
            if (s3[i - 1] == s1[i - 1]) {
                f[i][0] = true;
            }
        }
        for (int j = 1; j <= n; j++) {
            if (s3[j - 1] == s2[j - 1]) {
               f[0][j] = true;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (f[i - 1][j] == true && s3[i + j - 1] == s1[i - 1]) {
                    f[i][j] = true;
                }
                if (f[i][j - 1] == true && s3[i + j - 1] == s2[j - 1]) {
                    f[i][j] = true;
                }
            }
        }
        return f[m][n];
    }
};