preposterous.java

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

import java.util.Scanner;


/**
 * ID:1240
 * 前序后续遍历
 * @author yhm
 *
 */
public class PrePosterous {

	static int m;
	static int[] C;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			m = cin.nextInt();
			if(m==0){
				break;
			}
			
			C = new int[m+1];
			initC();
			
			String preOrder = cin.next();
			String postOrder = cin.next();
			long result = getNum(preOrder,postOrder);
			System.out.println(result);
			
		}
		

	}

	
	static long getNum(String preOrder,String postOrder){
		if(preOrder.length()==0){
			return 1;
		}
		else if(preOrder.length()==1){
			return 1;
		}
		int i = 0;
		long result = 1;
		while(preOrder.length()>1){
			char first = preOrder.charAt(1);
			int index = postOrder.indexOf(first);
			String newPostOrder = postOrder.substring(0,index+1);
			postOrder = postOrder.substring(index+1);
			String newPreOrder = preOrder.substring(1, 1+newPostOrder.length());
			preOrder = preOrder.charAt(0) + preOrder.substring(1+newPostOrder.length());
			
			result*=getNum(newPreOrder,newPostOrder);
			i++;
		}
		result*=C[i];
		return result;

	}
	
	static void initC(){
		C[0] = 1;
		C[1] = m;
		for(int i=2;i<=m;i++){
			if(m-i<i){
				C[i] = C[m-i];
			}
			else{
				C[i] = (C[i-1]*(m-i+1))/i;
			}
		}
	}
	
}