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

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.