[Java] concise O(n) space solution with minor optimization converted from pure DFS


  • 0
    S
    1. A minor optimization can be exchanging s1 with s2 when s1.length is smaller than s2.length. In this way, we can save some space when initializing a 1D dp array.

    2. I was stuck in TLE by my DFS version solution, finally, I reached this dp version by converting my original one. Hopefully, it can help. :)

      public boolean isInterleave(String s1, String s2, String s3) {
      int len1 = s1.length();
      int len2 = s2.length();
      int len3 = s3.length();
      if (len1 + len2 != len3) {
      return false;
      }
      if (len1 < len2) {
      // to save space for dp array
      return isInterleave(s2, s1, s3);
      }
      boolean[] dp = new boolean[len2 + 1];
      for (int i = len1; i >= 0; i--) {
      for (int j = len2; j >= 0; j--) {
      int k = i + j;
      if (k == len3) {
      dp[j] = true;
      } else {
      dp[j] = (i < len1 && s1.charAt(i) == s3.charAt(k) && dp[j])
      // able to match s3[k] using s1[i] ?
      ||
      (j < len2 && s2.charAt(j) == s3.charAt(k) && dp[j + 1]);
      // able to match s3[k] using s2[j] ?
      }
      }
      }

      return dp[0];
      

      }

    Originally TLE backtracking version:

    public class SolutionDFS {
    	public boolean isInterleave(String s1, String s2, String s3) {
    		int len1 = s1.length();
    		int len2 = s2.length();
    		int len3 = s3.length();
    		if (len1 + len2 != len3) {
    			return false;
    		}
    		// backtracking
    		return isInterleave(s1, s2, s3, 0, 0);
    	}
    
    	private boolean isInterleave(String s1, String s2, String s3, 
    			int i, int j) {
    		// base base
    		int k = i + j;
    		if (k == s3.length()) {
    			return true;
    		}
    
    		// recursive case: next character may be from either s1 or s2
    		return ((i < s1.length() && s1.charAt(i) == s3.charAt(k) && 
    				isInterleave(s1, s2, s3, i + 1, j)) || 
    				(j < s2.length() && s2.charAt(j) == s3.charAt(k) && 
    				isInterleave(s1, s2, s3, i, j + 1)));
    	}
    
    }

Log in to reply
 

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