Searching the number in the phone book

Problem

If I type some numbers in my cell, all phone numbers which have these typed numbers in any order should appear, tell data structure for this. 

Example: if I type 926 then 

932678.... 

92678... 

9777726.... 

should appear. 

Let me clear it through another example 

eg: i enter 321, then 

o/p(if they are in book) 

9344241.. 

972153....

This is similar to the T9 keyboard problem, but this time the query string is not look up sequentially.

  In this question, we are checking if the numbers in the query string existing in the phone numbers in the phone book.

  Because of this requirement, we can't use any tree or Trie for the search.
Only way left is to checking each phone numbers in the dictionary to see if it matches the query string.

  Fastest way to check if a digit exists in the target number is using the hash table, which provides $O(1)$ lookup time.

  We can initialize our phone book with the input numbers with the hash table recording the occurrence of the digits.

  Once this is done, searching for the given number in the phone book can be done in $O(N)$ or $O(KN)$, where N is the number of phone numbers in the phone book and K is the length of the query.

If I can come up with the faster way to do this job, I will write the follow-up post.

Here is the complete code in C++.

	#include <iostream>
	#include <vector>
	#include <string>
	using namespace std;
	struct node{
	short hashtable[10];
	string value;
	node(string v) : value(v){
	memset(hashtable, 0, 10 * sizeof(short));
	}
	};
	vector<string> search_numbers(string* input, int len, string query)
	{
	vector<string> result;
	vector<node*> dic;
	int i, j;
	for (i = 0; i < len; i++)
	{
	string num = input[i];
	node * n = new node(input[i]);
	for (int j = 0; j < num.length(); j++)
	{
	n->hashtable[num[j] - '0'] += 1;
	}
	dic.push_back(n);
	}
	short query_hash[10];
	memset(query_hash, 0, 10 * sizeof(short));
	for (j = 0; j < query.length(); j++)
	{
	query_hash[query[j] - '0']++;
	}
	for (i = 0; i < dic.size(); i++)
	{
	bool found = true;
	node * cur = dic[i];
	for (j = 0; j < query.length(); j++)
	{
	if (cur->hashtable[query[j] - '0'] < query_hash[query[j] - '0'])
	{
	found = false;
	break;
	}
	}
	if (found)
	{
	result.push_back(dic[i]->value);
	}
	}
	return result;
	}
	int main()
	{
	string input[5] = { "932678", "92678", "9777726", "9344241", "972153" };
	vector<string> found;
	found = search_numbers(input, 5, "926");
	cout << " search for 926: " << endl;
	for (int i = 0; i < found.size(); i++)
	cout << found[i]<<", ";
	cout << endl;
	found = search_numbers(input, 5, "321");
	cout << " search for 321: " << endl;
	for (int i = 0; i < found.size(); i++)
	cout << found[i]<<", ";
	cout << endl;
	return 1;
	}

view raw search_phone_number.cpp hosted with ❤ by GitHub

Practice statistics:

8 mins: to think up the algorithm and write part of code

15 mins: to complete the code and find one logical flaw


UPDATE (2019-06-03): Tried the same question again.

Here is python solution:
Could not find the better solution than $O(N)$ running time.

	class PhoneBook:
	# will ignore duplcate number test for now. To do that we need hash table for O(N) search.
	numbers = {}
	def add(self, number):
	map = {}
	for i in number:
	map[i] = 1 if i not in map else map[i] + 1
	self.numbers[number] = map
	def search(self, target):
	found = []
	target_map = {}
	for i in target:
	target_map[i] = 1 if i not in target_map else target_map[i] + 1
	for i in self.numbers:
	map = self.numbers[i]
	n = None
	for t in target_map:
	if t not in i or target_map[t] > map[t]:
	n = None
	break
	n = i
	if n != None:
	found.append(n)
	return found
	p = PhoneBook()
	input = ['9716123432', '9326784444', '9267801111', '9777726444', '9344241111', '9721536666']
	for i in input:
	p.add(i)
	query = '926'
	print ("query = {}, found = {}".format(query, p.search(query)))
	query = '321'
	print ("query = {}, found = {}".format(query, p.search(query)))

view raw phone_book.py hosted with ❤ by GitHub