An elegant python solution with DP


  • 3
    C

    Basic idea is starting from left most character of string, increase the index, if s[:idx+1] is a valid word, try generate all combinations of s[idx+1:]. Continue doing this until index reaches the end of string. This is a recursive solution, so each time all word break options are calculated, cache them.

    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def wordBreak(self, s, dict):
            self.dict = dict
            self.cache = {}
            return self.break_helper(s)
            
        def break_helper(self, s):
            combs = []
            if s in self.cache:
                return self.cache[s]
            if len(s) == 0:
                return []
                
            for i in range(len(s)):
                if s[:i+1] in self.dict:
                    if i == len(s) - 1:
                        combs.append(s[:i+1])
                    else:
                        sub_combs = self.break_helper(s[i+1:])
                        for sub_comb in sub_combs:
                            combs.append(s[:i+1] + ' ' + sub_comb)
                        
            self.cache[s] = combs
            return combs

  • 0
    V

    wa, we have very close answer:

    class Solution:
    
      def __init__(self):
        self.saved = {}
    
      def wordBreak(self, s, dict):
        self.saved.clear()
        size = len(s)
        return self.wordBreakImpl(s, dict)
    
      def wordBreakImpl(self, s, dict):
        if s in self.saved:
          return self.saved[s]
        else:
          ret = []
          for i in range(0, len(s)):
            subs = s[0:i+1]
            if subs in dict:
              if (i + 1) == len(s):
                currResult = [s]
              else:
                sentences = self.wordBreakImpl(s[i+1:], dict)
                currResult = map(lambda s: subs + " " + s, sentences)
              ret += currResult
    
          self.saved[s] = ret
          return ret

  • 0
    N

    I guess your code will TLE when input is:
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    ["a", "aa", "aaa", "aaaa", "aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaaa","aaaaaaaaaaaa"]
    the code

    for sub_comb in sub_combs:
    

    sub_combs may be very large


  • 0
    L

    Why? Any solution needs to traverse all possible splits. If you think this one is too slow, could share your faster solution?


  • 0
    L
    This post is deleted!

  • 0
    L

    Same idea, but bottom-up DP.
    With optimization in only checking all possible word length in the following line.

     for wordLen in wordLenList:
    

    AC in 46 ms. Full solution

    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def wordBreak(self, s, dict):
            sentences = [[] for i in range(len(s))]
            wordLenList = set(map(len, dict))
            for startIndex in xrange(len(s) - 1, -1, -1):
                for wordLen in wordLenList:
                    if startIndex + wordLen > len(s) or s[startIndex: startIndex + wordLen] not in dict:
                        continue
                    if startIndex + wordLen == len(s):
                        sentences[startIndex].append(s[startIndex: startIndex + wordLen])
                    else:
                        for sentence in sentences[startIndex + wordLen]:
                            sentences[startIndex].append(s[startIndex: startIndex + wordLen] + " " + sentence)
            return sentences[0]

  • 0
    D

    It fails the new test case baaaaa....


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.