单词混合

描述

一天小明和小红在玩单词混合的游戏，游戏的规则是按顺序给出3个单词，判断第3个单词是否能够由前两个单词中的所有字母混合而成。
前两个单词可以任意混合，但是混合后，原本两个单词中的字符前后顺序必须与原单词中的顺序保持一致。

输入

输入的第一行为一个正整数n（1<=n<=1000），表示测试样例的个数。 接下来n行，每行输入输入3个字符串，字符串之间由一个空格分隔，所有的字符串仅由英文大小写字母组成，区分大小写，即'A' != 'a'。 
输入数据保证第3个字符串的长度是前两个字符串长度之和，前两个字符串的长度范围是[1,200]。

输出

对于每个输入样例，首先输出“Case N: ”，N表示样例序号，从1开始。 如果第3个单词能够按照要求由前两个单词中的所有字母混合而成，则紧接着输出“yes”，否则输出“no”。

样例输入1

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

样例输出1

Case 1: yes
Case 2: yes
Case 3: no

import java.util.Scanner;   //深度优先搜索 

public class Main {

	static String word1,word2,mixWord;
	static int lengthm,length1,length2;
	
	//将混合字符串逐个字母与单词1单词2当前字母比较
	public static boolean compare(int w1,int w2,int mW) {
		int i;
		for (i = mW; i < lengthm; i++) {
			char chm = mixWord.charAt(i);
			//计算相等个数的计数器
			int count = 0;
			if (w1 < length1 && chm == word1.charAt(w1))		
				count++;
			if (w2 < length2 && chm == word2.charAt(w2))
				count++;
			//如果一个相等的都没有为假
			if (count == 0)
				break;
			//如果只等于单词1，将单词1下标加1
			else if (count == 1 && w1 < length1 && chm == word1.charAt(w1))
				w1++;
			//如果只等于单词2，将单词2下标加1
			else if (count == 1 && w2 < length2 && chm == word2.charAt(w2))
				w2++;
			//如果两个都等于，选能走到最后的，搜索开始
			else {
				if (compare(w1 + 1, w2, i + 1))
					return true;
				if (compare(w1, w2 + 1, i + 1))
					return true;
				//都走不到最后为假
				return false;
			}			
		}
		if (i == lengthm)
			return true;
		else
			return false;
	}
		
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int num = 1;
		while (num <= n) {
			word1 = input.next();
			word2 = input.next();
			mixWord = input.next();
			lengthm = mixWord.length();
			length1 = word1.length();
			length2 = word2.length();
			if (compare(0, 0, 0))
				System.out.println("Case " + num + ": yes");
			else
				System.out.println("Case " + num + ": no");
			num++;
		}
	}
}