<s> class Solution : <EOL> def wordBreak ( self , s , dict ) : <EOL> n = len ( s ) <EOL> possible = [ False for _ in xrange ( n ) ] <EOL> valid = [ [ False ] * n for _ in xrange ( n ) ] <EOL> for i in xrange ( n ) : <EOL> if s [ : i + <NUM_LIT:1> ] in dict : <EOL> possible [ i ] = True <EOL> valid [ <NUM_LIT:0> ] [ i ] = True <EOL> for j in xrange ( i ) : <EOL> if possible [ j ] and s [ j + <NUM_LIT:1> : i + <NUM_LIT:1> ] in dict : <EOL> valid [ j + <NUM_LIT:1> ] [ i ] = True <EOL> possible [ i ] = True <EOL> result = [ ] <EOL> if possible [ n - <NUM_LIT:1> ] : <EOL> self . genPath ( s , valid , <NUM_LIT:0> , [ ] , result ) <EOL> return result <EOL> def genPath ( self , s , valid , start , path , result ) : <EOL> if start == len ( s ) : <EOL> result . append ( "<STR_LIT:U+0020>" . join ( path ) ) <EOL> return <EOL> for i in xrange ( start , len ( s ) ) : <EOL> if valid [ start ] [ i ] : <EOL> path += [ s [ start : i + <NUM_LIT:1> ] ] <EOL> self . genPath ( s , valid , i + <NUM_LIT:1> , path , result ) <EOL> path . pop ( ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> print Solution ( ) . wordBreak ( "<STR_LIT>" , [ "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" ] ) </s>
