CareerCup

Trie is the simple solution for the simple developers ;)

The small challenge comes when pressing 'J' to search should show you names like "John May" and "May, John" as well (two Tries can solve it somehow).

A bigger one comes when the 'J' can be anywere in the name. Trie is out of scope in this case (as far as I see).

And the real one comes when it is a phonebook with Chinese names (oh, yeah, the World is not ASCII, it is Unicode!) and you have to search for "li" (read: show names where the pronounciation of the stored Chinese/Unicode character starts as "li")

Another interpretation can be that the key sequence should match the letter that are on the key - e.g. '2' should be OK for 'a' or 'b' or 'c' and so on. So '25' should match "Al". The word "telephone keypresses" suggest this kind of interpretation.

Oh, and another issue to handle with Tries is the letters that are treated as equals when matching - like n and ñ, but they are different in the real names.

This is one using trie.

geeksforgeeks.org/forum/topic/trie-print-whole-trie-auto-complete-given-a-string-perform-auto-complete?replies=1#post-39421

READ IT : "en.wikipedia.org/wiki/Trie"
this data structure is used to do the job you mentioned in question in linear time.

Tried would be used just for storing the dictionary. The other major part of the problem is to come up with all the possible letter combinations from the key-presses. Eg. 1 can {A,B,C} etc. ... this can be done using recursion.

int get_possible_characters(int, int&);

void generate_words(int* arr, int begin, int length, char* word=null)
{
	if(begin >= end)
	{
		printf("%s\n",word);
	}
	else
	{
		if(!word)
		{
			word = new char[length];
		}
		int num_candidates;
		char* candidates = get_possible_characters(a[begin], num_candidates);
		for(int i=0; i < num_candidates; i++)
		{
			word[begin] = candidates[i];
			generate_words(arr,begin+1,length,word);
		}
	}
	return;
}

int main()
{
	char* arr = new char[100];
	//Insert values in arr
	generate_words(arr,0,100);
}