Corrispondenza del modello di stringa dalla tabella di ricerca - Soluzione non esponenziale?

2

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?

    
posta Kevin 14.06.2016 - 20:23
fonte

0 risposte