<s> class Solution : <EOL> def minCut ( self , s ) : <EOL> lookup = [ [ False for j in xrange ( len ( s ) ) ] for i in xrange ( len ( s ) ) ] <EOL> mincut = [ len ( s ) - <NUM_LIT:1> - i for i in xrange ( len ( s ) + <NUM_LIT:1> ) ] <EOL> for i in reversed ( xrange ( len ( s ) ) ) : <EOL> for j in xrange ( i , len ( s ) ) : <EOL> if s [ i ] == s [ j ] and ( j - i < <NUM_LIT:2> or lookup [ i + <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] ) : <EOL> lookup [ i ] [ j ] = True <EOL> mincut [ i ] = min ( mincut [ i ] , mincut [ j + <NUM_LIT:1> ] + <NUM_LIT:1> ) <EOL> return mincut [ <NUM_LIT:0> ] <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> print Solution ( ) . minCut ( "<STR_LIT>" ) </s>
