UVa 156

From Algorithmist
Jump to: navigation, search

156 - Ananagrams[edit]

Summary[edit]

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

Explanation[edit]

  • 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.

Implementations[edit]

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

Input[edit]

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
#

Output[edit]

Disk
NotE
derail
drIed
eye
ladder
soon

Solutions[edit]