Simple java solution with DP using space O(n)


  • 2
    D
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();
        char[] c = s3.toCharArray();
    
        boolean[] dp = new boolean[a.length + 1];
        dp[0] = true;
        for (int i = 0; i < dp.length - 1; i++)
            dp[i + 1] = dp[i] && a[i] == c[i];
    
        for (int j = 1; j <= b.length; j++) {
            dp[0] = dp[0] && b[j - 1] == c[j - 1];
    
            for (int i = 1; i <= a.length; i++)
                dp[i] = dp[i - 1] && a[i - 1] == c[i + j - 1] || dp[i] && b[j - 1] == c[i + j - 1];
        }
        return dp[a.length];
    }

Log in to reply
 

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