首页 > 专题系列 > Java解POJ > POJ 2681 Anagrammatic Distance [解题报告] Java
2013
11-11

POJ 2681 Anagrammatic Distance [解题报告] Java

Anagrammatic Distance

问题描述 :

Two words are said to be anagrams of each other if the letters from one word can be rearranged to form the other word. For example, occurs is an anagram of succor; however, dear is not an anagram of dared (because the d appears twice in dared, but only once in dear). The most famous anagram pair (in English) is dog and god.

The anagrammatic distance between any two words is the minimum number of letters which must be removed so that the remaining portions of the two words become anagrams. For example, given the words sleep and leap, we need to remove a minimum of three letters —two from sleep and one from leap —before what’s left are anagrams of each other (in each case, lep). With words such as dog and cat, where the two have absolutely no letters in common, the anagrammatic distance is an extreme (explicitly 6) since all the letters need to be removed. (Here, a word is always an anagram of itself.)

You must write a program to calculate the anagrammatic distance between any two given words.

输入:

The first line of the input will contain a positive integer value N (less than 60,000) indicating the number of cases. Each case will consist of two words, possibly empty, each given on a single line (for a total of 2N additional lines).

Although they may have zero length, the words are simple —the letter are all lowercase and are taken from the usual twenty-six letter English alphabet (abcdefghijklmnopqrstuvwxyz). The longest word is pneumonoultramicroscopicsilicovolcanoconiosis.

输出:

The output should consist of the case number and the anagrammatic distance, formatted as shown.

样例输入:

4
crocus
succor
dares
seared
empty

smell
lemon

样例输出:

Case #1:  0 
Case #2:  1 
Case #3:  5  
Case #4:  4  

解题代码:

//* @author: [email protected]
import java.util.Scanner;
class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  in.nextLine();
  int u=0;
  while((a--)!=0)
  {
	u++;
	int[] p=new int[26];
	String s1=in.nextLine();
	String s2=in.nextLine();
	for(int i=0;i< s1.length();i++)
	{
		int t=s1.charAt(i)-'a';
		p[t]++;
	}
	for(int i=0;i< s2.length();i++)
	{
		int t=s2.charAt(i)-'a';
		p[t]--;
	}
	int cnt=0;
	for(int i=0;i< 26;i++)
		cnt+=Math.abs(p[i]);
	System.out.println("Case #"+u+":  "+cnt+" ");
   }
 }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3