JAVA-------------Easy Version To Understand!!!!!!!!!!


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

Log in to reply
 

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