2 edited tags
| link
source | link

String Pattern Matching from Lookup Table - Non-Exponential Solution?

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

  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?