Sorry for the late reply. I was out for some days.
First thanks to those friends who mention the soundex. Since this is a
data structure question, I think just saying using soundex is not the
proper answer. :-) Also, to my understanding, soundex is good for
exact match, not approximate match
yes, we can use a min heap of size k to keep track of the top k matching
words.
On 3/28/07, Dhruva Sagar [EMAIL PROTECTED] wrote:
OK! I get it now.
In that case what we can do is instead of sorting the result, what we can
do is simply while performing a linear search for the words (that are
Hi, Kevin,
you can try soundex. compute each word's soundex, and store these
soundex, Listword in a HashMap. for a giving word, compute it's
soundex, and just find the soundex in the hashmap. It would cost O(1).
good luck.
On Mar 29, 9:49 am, Kevin [EMAIL PROTECTED] wrote:
This is from an
soundex?
http://en.wikipedia.org/wiki/Soundex
On 3/28/07, Kevin [EMAIL PROTECTED] wrote:
This is from an interview question, see how do you guys think of it:
Given a Enlgish word, how to find these words that pronounce similar
to it?
You can have some reasonable assumptions, such as:
to find the top k words (after computing d), u dont have to fully sort it. u
can use the linear selection algorithm to find k
and sort those d of those k words if u need the order by order of
closeness ( O(n +klgk)) or
u can use a B-tree and once the B-tree u just have to start from the
leftmost
another rejection heuristic mite be length or percentage of common letters
or edit distance
On 3/28/07, Arun [EMAIL PROTECTED] wrote:
to find the top k words (after computing d), u dont have to fully sort it.
u can use the linear selection algorithm to find k
and sort those d of those k
The dictionary will already be sorted, hence the output of a linear search
will already be sorted!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
i believe the sorted order needed is interms of how close they are and not
alphabetical? moreover the words neednot necc be in dictionary(like nouns)
On 3/28/07, Dhruva Sagar [EMAIL PROTECTED] wrote:
The dictionary will already be sorted, hence the output of a linear search
will already be
