2

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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.