zipper.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:2192
 * DP
 * @author yhm
 *
 */
public class Zipper {

	static String str1, str2, str;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=1;i<=caseNum;i++){
			str1 = cin.next();
			str2 = cin.next();
			str = cin.next();
			System.out.print("Data set "+i+": ");
			if(solve()){
				System.out.println("yes");
			}
			else{
				System.out.println("no");
			}
		}
	}
	
	static boolean solve(){
		int len1 = str1.length();
		int len2 = str2.length();

		boolean[][] array = new boolean[len1+1][len2+1];
		array[0][0] = true;
		for(int i=1;i<=len1;i++){
			array[i][0] = str1.substring(0, i).equals(str.substring(0, i));
		}
		for(int i=1;i<=len2;i++){
			array[0][i] = str2.substring(0, i).equals(str.substring(0, i));
		}
		
		
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
				if(!array[i-1][j] && !array[i][j-1]){
					array[i][j] = false;
				}
				else{
					if(array[i-1][j] && str1.charAt(i-1)==str.charAt(i+j-1)){
						array[i][j] = true;
						continue;
					}
					else if(array[i][j-1] && str2.charAt(j-1)==str.charAt(i+j-1)){
						array[i][j] = true;
						continue;
					}
				}
			}
		}
		
		return array[len1][len2];
		
	}

}