Returning a Subset of Strings from 10000 ascii strings

Question

My college is getting over so I have started preparing for the interviews to get the JOB and I came across this interview question while I was preparing for the interview

1. You have a set of 10000 ascii strings (loaded from a file)
2. A string is input from stdin.
3. Write a pseudocode that returns (to stdout) a subset of strings in (1) that contain the same distinct characters (regardless of order) as input in (2). Optimize for time.
4. Assume that this function will need to be invoked repeatedly. Initializing the string array once and storing in memory is okay . Please avoid solutions that require looping through all 10000 strings.

Can anyone provide me a general pseudocode/algorithm kind of thing how to solve this problem? I am scratching my head thinking about the solution. I am mostly familiar with Java.

Answer 1

Here is an O(1) algorithm!

Initialization:

• For each string, sort characters, removing duplicates - eg "trees" becomes "erst"
• load sorted word into a trie tree using the sorted characters, adding a reference to the original word to the list of words stored at the each node traversed

Search:

• sort input string same as initialization for source strings
• follow source string trie using the characters, at the end node, return all words referenced there