dp python beat 91%


  • 0
    class Solution(object):
        def break_word(self, s):
            if self.memo[len(s)]<>None:
                return self.memo[len(s)]
            for w in self.word_dict:
                if s.startswith(w) and self.break_word(s[len(w):]):
                    self.memo[len(s)] = True
                    return True
            self.memo[len(s)] = False
            return False
        def wordBreak(self, s, wordDict):
            self.word_dict = wordDict
            self.memo = [None]*(len(s)+1)
            self.memo[0] = True
            return self.break_word(s)
    

    key points

    1. use build-in function startwith.
    2. memo to avoid repeated calling.

  • 0

    startwith is much slower than slicing (string[a:b])


Log in to reply
 

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