It's not so interesting to publish ready code, but for those who stuck on this problem the following algorithm could be useful:

1. First of all, build generator, that will generate random tests with specified phone number length and number of words. It will helpful, since you don't know, which tests are runned when you send you code for check.

2. Convert your words to digits and remove those of them that aren't contained in phone number. Also remove duplications that can appear after this converting. During this process build dictionary that will contain converted word as a key, and original word as a value. Last one will be needed to output the result.

3. Sort converted words by length in descendent order.

4. Take every converted word and find all its inclusions to the phone number. Build dictionary that will contain found index as key and list of converted words as value.

5. Now use recursive function which initially will get index=0 as argument, find all words from dictionary for the index and loop them, taking their length to get next index.
If next index equals phone number length, you found one of the solutions.

6. Optimize the function to eleminate redundant calls. I mean, on specific step you can check if the next searched solution is expected to be better than found one or not.

I'm not sure that this algorithm is the best, but at least I got "accepted" on C# with 600 ms performance.