UVa 156

From Algorithmist

Contents 1 156 - Ananagrams 2 Summary 3 Explanation 4 Implementations 5 Input 6 Output

[edit] 156 - Ananagrams

• http://acm.uva.es/p/v1/156.html

[edit] Summary

Given a dictionary of words, find words that are not ananagrams within the context of the dictionary.

[edit] Explanation

• Create a dictionary and find each word that is not a permutation of another in the dictionary.
• If you went and looked for every permutation of each word and compared it to another, you would easily have an n! solution. And for n = 20 and 1000 words this will take a really long time.
• A simpler solution would be to sort the case insensitive words and compare them to each other.
• The words must be sorted lexigraphically.

[edit] Implementations

Use a map to hold the previous string and the modified uppercase/lowercase string. or you can use structure to store words and use qsort(quick sort) or sort(STL) to make it faster

[edit] Input

ladder came tape soon leader acme RIDE lone Dreis peat
 ScAlE orb  eye  Rides dealer  NotE derail LaCeS  drIed
noel dire Disk mace Rob dries
#

[edit] Output

Disk
NotE
derail
drIed
eye
ladder
soon