Dato il problema ...
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.
... è possibile calcolare in tempo polinomiale? Posso solo pensare a soluzioni esponenziali simili a ...
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)
... dove si scorre la stringa e ogni volta che viene trovata una corrispondenza nella tabella di ricerca, sostituirla con il carattere nella tabella di ricerca e chiamare in modo ricorsivo il metodo con il nuovo carattere e la sottostringa rimanente.
Non vedo come ci siano sottosistemi sovrapposti che consentirebbero la memoizzazione o la programmazione dinamica, o qualsiasi altro metodo per ridurre il numero grezzo di operazioni. C'è qualcosa che mi manca?