Simple java dp, O(n*m) time, O(min(n,m)) space, for your reference


  • 0
    C
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        if (n1 + n2 != n3) return false;
        if (n2 > n1) {
            String tmp = s1; s1 = s2; s2 = tmp;
            int n = n1; n1 = n2; n2 = n;
        }
        boolean cando[] = new boolean[n2+1];
        cando[0] = true;
        for (int j = 1; j <= n2; ++j)
            cando[j] = cando[j-1] && s3.charAt(j-1) == s2.charAt(j-1);
        for (int i = 1; i <= n1; ++i) {
            cando[0] = cando[0] && s3.charAt(i-1) == s1.charAt(i-1);
            for (int j = 1; j <= n2; ++j) {
                char c = s3.charAt(i + j - 1);
                cando[j] = (cando[j] && c == s1.charAt(i-1)) || (cando[j-1] && c == s2.charAt(j-1));
            }
        }
        return cando[n2];
    }

  • 0
    R

    Thanks for sharing. What is the Runtime (ms) you got?


  • 0
    C

    5ms. Thanks for commenting.


Log in to reply
 

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