palindrome

gistfile1.txt

s = 'xyabax'

d0 = dict()
d1 = dict()

def calc0(s):
    global inf 
    inf = len(s) + 1
    return calc(s)

def calc(s):
    if len(s) == 0:
        return 0, 0
    if len(s) == 1:
        return 1, 1

    if s in d0:
        return d0[s], d1[s]
    else:
        if s[0] == s[-1]:
            d1[s] = calc(s[1:-1])[0]
        else:
            d1[s] = inf
        candidates = [(calc(s[0:i])[0] + calc(s[i:])[0]) for i in range(1, len(s))]
        candidates.append(d1[s])
        #print s, candidates
        d0[s] = min(candidates)
        return d0[s], d1[s]

print calc0('xyabax')
print calc0('caacadac')
print calc0('zabaefeghgpz')
print calc0('zabaxcdcyefexghgz')
print calc0('abacdc')