動機

不只一種dp

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = leetcode, wordDict = [leet,code]Output: trueExplanation: Return true because leetcode can be segmented as leet code.

Example 2:

Input: s = applepenapple, wordDict = [apple,pen]Output: trueExplanation: Return true because applepenapple can be segmented as apple pen apple.Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = catsandog, wordDict = [cats,dog,sand,and,cat]Output: false

 

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Sol

一個是把範圍標出來，之後列中點去二分 但這樣會割出很多一定不會過的字串，也會割出很多已經割過的字串

但還是AC

class Solution:
    @functools.lru_cache(None)
    def dp(self,i,j):
        if i < 0 or i >= len(self.s) or j < 0 or j > len(self.s):
            return False
        elif self.s[i:j] in self.ws:
            return True
        else:
            ret = False
            for k in range(i,j):
                ret = ret or self.dp(i,k) and self.dp(k,j)
            return ret
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.s, self.ws = s, wordDict
        return self.dp(0,len(s))

看input很明顯是像lisp的list那樣(一直cons單字)組成string的，所以我們應該也要這樣走!!

class Solution:
    @functools.lru_cache(None)
    def dp(self,s):
        if s in self.ws:
            return True
        else:
            for i in range(1,len(s)):
                if s[:i] in self.ws and self.dp(s[i:]):
                    return True
            return False
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.ws = wordDict
        return self.dp(s)