DP33 兩個字符串交叉得到的字符串 Find if a string is interleaved of two ot

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.

We have discussed a simple solution of this problem here. The simple solution doesn’t work if strings A and B have some common characters. For example A = “XXY”, string B = “XXZ” and string C = “XXZXXXY”. To handle all cases, two possibilities need to be considered.

a) If first character of C matches with first character of A, we move one character ahead in A and C and recursively check.

b) If first character of C matches with first character of B, we move one character ahead in B and C and recursively check.

If any of the above two cases is true, we return true, else false. Following is simple recursive implementation of this approach (Thanks to Frederic for suggesting this)

這是一系列的幾道題：

1 判斷c是否是由a和b交叉而得：

1. 遞歸 2 DP 3 3指針，但是當有重復字符出現時出錯！

2 打印出a和b交叉而得的所有組合：遞歸

package DP;

public class InterleaveStrings {

	public static void main(String[] args) {
		String s1 = "AB";
		String s2 = "CD";
		printTwoInterleavings(s1, s2, "");
		String s = "ACEB";
		System.out.println(isInterleavedNaive(s1, s2, s));
		System.out.println(isInterleavedRec(s1, s2, s));
		System.out.println(isInterleavedDP(s1, s2, s));
	}
	
	
	/*
	 Input: str1 = "AB",  str2 = "CD"
	 Output:
	    ABCD
	    ACBD
	    ACDB
	    CABD
	    CADB
	    CDAB
	 */
	public static void printTwoInterleavings(String s1, String s2, String soFar){
		if(s1.length()==0 && s2.length()==0){
			System.out.println(soFar);
			return;
		}
		if(s1.length() == 0){
			System.out.println(soFar + s2);
			return;
		}
		if(s2.length() == 0){
			System.out.println(soFar + s1);
			return;
		}
		printTwoInterleavings(s1.substring(1), s2, soFar+s1.charAt(0));
		printTwoInterleavings(s1, s2.substring(1), soFar+s2.charAt(0));
	}
	
	
	
	// O(2^n)
	public static boolean isInterleavedRec(String s1, String s2, String s){
		// Base Case: If all strings are empty
		if(s1.length()==0 && s2.length()==0 && s.length()==0){
			return true;
		}
		if(s.length() == 0){		// If s is empty and any of the two strings is not empty
			return false;
		}
		
		boolean b1 = false;
		boolean b2 = false;
		
		if(s1.length()!=0 && s.charAt(0)==s1.charAt(0)){
			b1 = isInterleavedRec(s1.substring(1), s2, s.substring(1));
		}
		if(s2.length()!=0 && s.charAt(0)==s2.charAt(0)){
			b2 = isInterleavedRec(s1, s2.substring(1), s.substring(1));
		}
		
		// If any of the above mentioned two possibilities is true,
	    // then return true, otherwise false
		return b1 || b2;
	}
	
	
	// A Dynamic Programming based program to check whether a string s is
	// an interleaving of two other strings s1 and s2.
	// O(L1*L2) time, space
	public static boolean isInterleavedDP(String s1, String s2, String s){
		int L1 = s1.length();		// Find lengths of the two strings
		int L2 = s2.length();
		int L = s.length();
		
		// Let us create a 2D table to store solutions of
	    // subproblems.  isIL[i][j] will be true if s[0..i+j-1]
	    // is an interleaving of s1[0..i-1] and s2[0..j-1].
		boolean[][] isIL = new boolean[L1+1][L2+1];
		
		// C can be an interleaving of A and B only of sum
	    // of lengths of A & B is equal to length of C.
		if(L1+L2 != L){
			return false;
		}
		
		for(int l1=0; l1<=L1; l1++){
			for(int l2=0; l2<=L2; l2++){
				// two empty strings have an empty string as interleaving
				if(l1==0 && l2==0){
					isIL[l1][l2] = true;
				}
				// A is empty
				else if(l1==0 && s2.charAt(l2-1)==s.charAt(l2-1)){
					isIL[l1][l2] = isIL[l1][l2-1];
				}
				// B is empty
				else if(l2==0 && s1.charAt(l1-1)==s.charAt(l1-1)){
					isIL[l1][l2] = isIL[l1-1][l2];
				}
				
				if(l1!=0 && l2!=0){
					// Current character of C matches with current character of A,
		            // but doesn't match with current character of B
					if(s.charAt(l1+l2-1)==s1.charAt(l1-1) && s.charAt(l1+l2-1)!=s2.charAt(l2-1)){
						isIL[l1][l2] = isIL[l1-1][l2];
					}
					// Current character of C matches with current character of B,
		            // but doesn't match with current character of A
					else if(s.charAt(l1+l2-1)==s2.charAt(l2-1) && s.charAt(l1+l2-1)!=s1.charAt(l1-1)){
						isIL[l1][l2] = isIL[l1][l2-1];
					}
					// Current character of C matches with that of both A and B
					else if(s.charAt(l1+l2-1)==s1.charAt(l1-1) && s.charAt(l1+l2-1)==s2.charAt(l2-1)){
						isIL[l1][l2] = isIL[l1-1][l2] || isIL[l1][l2-1];
					}
				}
			}
		}
		
		return isIL[L1][L2];
	}
	
	
	
	
	// Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.
	// This approach doesn’t work if A and B have some characters in common.
	// http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings/
	public static boolean isInterleavedNaive(String s1, String s2, String s){
		int i=0, j=0, k=0;
		while(k != s.length()){
			if(s.charAt(k) == s1.charAt(i)){
				i++;
			}else if(s.charAt(k) == s2.charAt(j)){
				j++;
			}else{
				return false;
			}
			k++;
		}
		if(i!=s1.length() || j!=s2.length()){
			return false;
		}
		return true;
	}
	
	

}