Typical DP iterative solution in Java with O(n) space.


  • 0
    L
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
            if(len3!=len1+len2) return false;
            boolean[] valid = new boolean[len2+1]; 
            valid[0] = true;
            for(int i = 0; i <= len1; i++) {
                if(i!=0) valid[0] = (valid[0] && s1.charAt(i-1)==s3.charAt(i-1))? true : false;
                for(int j = 1; j <= len2; j++) {
                    if(i!=0&&s3.charAt(i+j-1)==s1.charAt(i-1)&&valid[j] || s3.charAt(i+j-1)==s2.charAt(j-1)&&valid[j-1]) valid[j] = true;
                    else valid[j] = false;
                }
            }
            return valid[len2];
        }
    }

Log in to reply
 

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