Suppose you have an input string s and a list of strings. You can delete a character in the string (one at a time) if the resulting string after deletion is in the given list of strings. Is it possible to turn s into a single character string (note that single character must be present in the list of strings)?

Can this problem be solved in polynomial time? I could only think O(2^n).

This was a problem given in a HFT onsite interview.