Java super short and clean DP O(mn) time and O(n) space


  • 0
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1.length() + s2.length() != s3.length()) {
                return false;
            }
            int m = s1.length(), n = s2.length();
            boolean[][] isInterleave = new boolean[2][n + 1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    isInterleave[i % 2][j] = (i == 0 && j == 0) || 
                                         (i != 0 && s3.charAt(i + j - 1) == s1.charAt(i - 1) && isInterleave[(i - 1) % 2][j]) ||
                                         (j != 0 && s3.charAt(i + j - 1) == s2.charAt(j - 1) && isInterleave[i % 2][j - 1]);
                }
            }
            return isInterleave[m % 2][n];
        }
    }

Log in to reply
 

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