Interleaving String

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

Thoughts

这道题比较非主流。有三个str, 该如何设计f呢？直观的想一下，直接用f[i]s3前i个字符是否由s1和s2组成。这样没有反应s1和s2的信息。所以不如反过来想，选取s1的前i个，s2的前j个则s3也就固定了。于是f[i][j]为s1的前i个，s2的前j个是否构成了s3的前i+j个字符。

Code

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();

        if (s3.length() != m + n) {
            return false;
        }

        // f
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;

        // init
        for (int i = 1; i <= m; i++) {
            if (s1.charAt(i - 1) != s3.charAt(i - 1)) {
                break;
            }
            f[i][0] = true;
        }
        for (int j = 1; j <= n; j++) {
            if (s2.charAt(j - 1) != s3.charAt(j - 1)) {
                break;
            }
            f[0][j] = true;
        }

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

        return f[m][n];
    }
}

Analysis

TC: O(mn)