Given the problem...
Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all possible Strings.
...is it possible to compute in polynomial time? I can only think of exponential solutions similar to...
getStrings(String):
for (i = 0 -> String.length)
if (String.substring(0->i) in LookupTable)
String.replaceRange(0->i, LookupTable[String.substring(0->i)])
getStrings(String.substring(i, String.length)
...where we iterate through the string, and each time a match is found in the lookup table, replace with the character in the lookup table and recursively call the method with the new character and the remaining substring.
I don't see how there are overlapping sub-problems that would allow for memoization or dynamic programming, or any other method to reduce the raw number of operations. Is there something I'm missing?
