<s> class Solution : <EOL> def partition ( self , s ) : <EOL> n = len ( s ) <EOL> is_palindrome = [ [ <NUM_LIT:0> for j in xrange ( n ) ] for i in xrange ( n ) ] <EOL> for i in reversed ( xrange ( <NUM_LIT:0> , n ) ) : <EOL> for j in xrange ( i , n ) : <EOL> is_palindrome [ i ] [ j ] = s [ i ] == s [ j ] and ( ( j - i < <NUM_LIT:2> ) or is_palindrome [ i + <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] ) <EOL> sub_partition = [ [ ] for i in xrange ( n ) ] <EOL> for i in reversed ( xrange ( n ) ) : <EOL> for j in xrange ( i , n ) : <EOL> if is_palindrome [ i ] [ j ] : <EOL> if j + <NUM_LIT:1> < n : <EOL> for p in sub_partition [ j + <NUM_LIT:1> ] : <EOL> sub_partition [ i ] . append ( [ s [ i : j + <NUM_LIT:1> ] ] + p ) <EOL> else : <EOL> sub_partition [ i ] . append ( [ s [ i : j + <NUM_LIT:1> ] ] ) <EOL> return sub_partition [ <NUM_LIT:0> ] <EOL> class Solution2 : <EOL> def partition ( self , s ) : <EOL> result = [ ] <EOL> self . partitionRecu ( result , [ ] , s , <NUM_LIT:0> ) <EOL> return result <EOL> def partitionRecu ( self , result , cur , s , i ) : <EOL> if i == len ( s ) : <EOL> result . append ( list ( cur ) ) <EOL> else : <EOL> for j in xrange ( i , len ( s ) ) : <EOL> if self . isPalindrome ( s [ i : j + <NUM_LIT:1> ] ) : <EOL> cur . append ( s [ i : j + <NUM_LIT:1> ] ) <EOL> self . partitionRecu ( result , cur , s , j + <NUM_LIT:1> ) <EOL> cur . pop ( ) <EOL> def isPalindrome ( self , s ) : <EOL> for i in xrange ( len ( s ) / <NUM_LIT:2> ) : <EOL> if s [ i ] != s [ - ( i + <NUM_LIT:1> ) ] : <EOL> return False <EOL> return True <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> print Solution ( ) . partition ( "<STR_LIT>" ) </s>
