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

by Kevin   Last Updated December 03, 2017 19:05 PM

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?



Related Questions



tail-recursion over recursion for general use

Updated May 26, 2015 23:02 PM

Time complexity analysis for recurrence relation

Updated July 28, 2015 16:39 PM