Question: https://oj.leetcode.com/problems/word-break-ii/
Question Name: Word Break II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | class Solution: # @param s, a string # @param dict, a set of string # @return a boolean def _isBreakable(self, s, dict): ''' Solve it with dynamic programming. ''' couldBreak = [False] * len(s) for breakAfterCurrent in xrange(len(s)): if s[: breakAfterCurrent+1] in dict: # The substring from beginning to here is in the dict. # We can make a break between this position and its # next position. couldBreak[breakAfterCurrent] = True continue # Otherwise, we will try to check, whether this substring # s[:breakAfterCurrent+1] could be composed by breakable # head and a tail, which is in the dict. for preBreak in xrange(breakAfterCurrent): if couldBreak[preBreak] == False: # The head is not breakable continue elif s[preBreak+1: breakAfterCurrent+1] not in dict: # The tail is not in the dict. continue else: # As long as we know it's breakable, no need to # continue the search for current position. couldBreak[breakAfterCurrent] = True break return couldBreak[-1] # @param s, a string # @param dict, a set of string # @return a list of strings def wordBreak(self, s, dict): ''' Solve it with dynamic programming. ''' # First of all, use a much-less-time-consuming method to check # whether the answer is an empty list. # It is important to pass some unbreakable tests. if not self._isBreakable(s, dict): return [] sLen = len(s) couldBreak = [[] for _ in xrange(sLen)] # There may be multiple candidates in dict, having the same length. # So we are using set to find out the unique ones. # This is an optimization. Without this, we can still pass all # the tests by trying all lengths. candidateLen = set([len(item) for item in dict]) for breakAfterCurrent in xrange(sLen): if s[: breakAfterCurrent+1] in dict: # The substring from beginning to here is in the dict. # We can make a break between this position and its # next position. couldBreak[breakAfterCurrent].append([s[: breakAfterCurrent+1]]) # Otherwise, we will try to check, whether this substring # s[:breakAfterCurrent+1] could be composed by breakable # head and a tail, which is in the dict. for preBreak in candidateLen: preBreak = breakAfterCurrent - preBreak if preBreak < 0: # Not enough characters. continue elif couldBreak[preBreak] == []: # The head is not breakable continue elif s[preBreak+1: breakAfterCurrent+1] not in dict: # The tail is not in the dict. continue else: combinations = [item +[s[preBreak+1: breakAfterCurrent+1]] for item in couldBreak[preBreak]] couldBreak[breakAfterCurrent].extend(combinations) return [" ".join(combination) for combination in couldBreak[-1]] |