atcoder之A Great Alchemist

C - A Great Alchemist

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Problem

Carol is a great alchemist.

In her world, each metal has a name of 2N (N is an integer) letters long, which consists of uppercase alphabets.

Carol can create metal S3 from S1 and S2 alchemical when she can make the name of S3 by taking N letters each from S1 and S2then rearranging them properly.

You are given 3 names of the metal S1, S2, S3. Determine wether Carol can create S3 from S1 and S2 or not.

Input

The input will be given in the following format from the Standard Input.

S1
S2
S3

On the first line, you will be given the name of the first metal material S1.
On the second line, you will be given the name of the second metal material S2.
On the third line, you will be given the name of the metal S3, which Carol wants to create.
Each character in the S1, S2, and S3 will be an uppercase English alphabet letter.
Each string S1, S2 and S3 has same number of letters and the number is always even.
It is guaranteed that 2≦|S1|≦105

Output

If Carol can create S3 from S1 and S2, output YES, if not, output NO in one line. Make sure to insert a line break at the end of the output.

Input Example 1

AABCCD
ABEDDA
EDDAAA

Output Example 1

YES

You can make EDDAAA by picking AAD from the first metal, and AED from the second metal.

Input Example 2

AAAAAB
CCCCCB
AAABCB

Output Example 2

NO

To make AAABCB, you have to take at least four letters from the first material. So this can't be created alchemical.

思路：採用回溯法，在回溯法之前能够剪枝的。

剪枝：1假设array1[i]+array2[i]<array3[i]，直接输出NO；

2commonS1S3为Math.min(array1[i],array3[i]) (i=0,1,...,n-1) 求和，

commonS2S3为Math.min(array2[i],array3[i]) (i=0,1,...,n-1) 求和。

假设commonS1S3和commonS2S3分别小于n/2。直接输出NO。

import java.util.*;

public class Main {
	private static final int letter_count = 26;

	public static boolean backTracking(String s3, int[] array1, int[] array2,
			int count1, int count2, int curIndex) {
		if (curIndex >= s3.length()) // 所有试探结束
			return true;
		int index = s3.charAt(curIndex) - 'A'; // curIndex所相应的下标

		// 假设array1[index]中没有须要的元素，同一时候count1（在s1中已经用掉的字符个数）小于n/2
		if (array1[index] > 0 && count1 <= s3.length() / 2) {
			array1[index]--; // 用掉s1中一个字符
			if (backTracking(s3, array1, array2, count1 + 1, count2,
					curIndex + 1))
				return true;
			array1[index]++; // 回溯
		}
		if (array2[index] > 0 && count2 <= s3.length() / 2) {
			array2[index]--;
			if (backTracking(s3, array1, array2, count1, count2 + 1,
					curIndex + 1))
				return true;
			array2[index]++;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str1 = sc.next();
		String str2 = sc.next();
		String str3 = sc.next();
		int[] num1 = new int[letter_count];
		int[] num2 = new int[letter_count];
		int[] num3 = new int[letter_count];
		boolean flag = true;
		int commonS1S3 = 0;
		int commonS2S3 = 0;
		for (int i = 0; i < str1.length(); i++) {
			num1[str1.charAt(i) - 'A']++;
			num2[str2.charAt(i) - 'A']++;
			num3[str3.charAt(i) - 'A']++;

		}
		for (int i = 0; i < letter_count; i++) {
			if (num1[i] + num2[i] < num3[i]) 
				flag = false;
			
			commonS1S3 += Math.min(num1[i], num3[i]);
			commonS2S3 += Math.min(num2[i], num3[i]);
		}
		if (2 * commonS1S3 < str1.length() || 2 * commonS2S3 < str1.length())
			flag = false;
		if (flag)
			flag = backTracking(str3, num1, num2, 0, 0, 0);
		if (flag)
			System.out.println("YES");
		else
			System.out.println("No");
	}