def geneToSymbol(s, mapping):
memo = {len(s): ['']}
# -----------------------------------------
def parseSuffix(i):
if i in memo:
# parseSuffix(i) has been computed before, directly use look-up table
return memo[i]
else:
memo[i] = []
# check each possible suffix index
for j in range(i+1, len(s)+1):
# scan each parsing result
for tail in parseSuffix(j):
if s[i:j] in mapping:
# prefix s[i:j] can be parsed
memo[i].append( reverse_table[s[i:j]] + tail )
return memo[i]
# -----------------------------------------
return parseSuffix(0)
source = "CGTGATTACG"
#source = "TACGTT"
#source = "TTCGTTT"
table = {"A":"CGT", "B":"TACG", "C":"TT", "D":"GAT"}
## dictionary
# key: gene
# value: upper case symvol
reverse_table = { v: k for k,v in table.items()}
result = geneToSymbol(source, reverse_table)
print(result)