palindrome

gistfile1.py

s = 'xyabax'

d = dict()

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

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

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

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