Problem B - Anagrams
--------------------
An anagram is a word or phrase formed by rearranging the letters of
another word or phrase. For example, "carthorse" is an anagram of
"orchestra". Blanks within a phrase are ignored in forming anagrams.
Thus, "orchestra" and "horse cart" are also anagrams. Note that a phrase
is an anagram of itself.
Write a program that reads a list of phrases and prints all pairs of
anagrams occurring in the list.
Input
-----
The first line of the input will contain a single integer indicating the
number of test cases you need to test. The second line will be blank.
Each test case will consist of from 1 to 100 lines. A blank line signals
the end of a test case. Each line constitutes one phrase and will be at
most 255 characters long. All phrases will be in lower case.
Output
------
Some number of lines (including possibly 0 if there are no anagrams in
the list), each line containing two anagrammatic phrases separated by
'='.
Each anagram pair should be printed exactly once, and the order of the
output must be lexicographic, as shown in the sample output below.
After the output for each test case, output a blank line. If a test
case, contains no anagrams, only this blank line should be produced.
Sample Input
------------
3
carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra
fire
ice
power
woper
Output for Sample Input
-----------------------
carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut
power = woper
Saturday, June 27, 2009
64. ANAGRAMS
Subscribe to:
Post Comments (Atom)
1 comments:
JAVA sol: for ANAGRAMS
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class B
{
void Begin()
{
String numberS = ReadLn(255);
int number = Integer.parseInt(numberS.trim());
ReadLn(255);
for (int z = 0; z LT number; z++)
{
ArrayList l = new ArrayList();
String line = ReadLn(255);
while (line.length()GT0)
{
l.add(line);
line = ReadLn(255);
}
Collections.sort(l);
for (int i=0;iLTl.size();i++)
{
for (int j=i+1;jLTl.size();j++)
{
String s1 = (String) l.get(i);
String s2 = (String) l.get(j);
if (anagram(s1.trim(),s2.trim()))
System.out.println(s1 + " = " + s2);
}
}
System.out.println();
}
}
boolean anagram(String s1, String s2)
{
//System.out.println(s1 + "---" + s2);
for (int i=0;iLTs1.length();i++)
{
char c = s1.charAt(i);
if (c == ' ') continue;
int pos = s2.indexOf(c);
if (pos == -1) return false;
else s2 = s2.substring(0,pos) + s2.substring (pos+1);
}
for (int j=0;jLTs2.length();j++)
{
if (s2.charAt(j) != ' ') return false;
}
return true;
}
static String ReadLn(int maxLg) // utility function to read from stdin
{
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg LT maxLg)
{
car = System.in.read();
if ((car LT 0) || (car == '\n'))
break;
lin[lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0))
return (null); // eof
return (new String(lin, 0, lg));
}
public static void main(String args[]) // entry point from OS
{
B myWork = new B(); // create a dynamic instance
myWork.Begin(); // the true entry point
}
}
Post a Comment