Word Break

Subject to

Given a target string and a set of strings, determine whether the target string can be split into several strings that are in the given set of strings.

Their thinking

Dynamic programming

code

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(n):
            for j in range(i, -1, -1):
                print j, i, s[j:i + 1], dp
                if dp[j] and s[j:i + 1] in wordDict:
                    dp[i + 1] = True
                    break
            print '-----loop-----'
        return dp[n]
Copy the code

Output:

0 0 l [True, False, False, False, False, False, False, False, False]
-----loop-----
1 1 e [True, False, False, False, False, False, False, False, False]
0 1 le [True, False, False, False, False, False, False, False, False]
-----loop-----
2 2 e [True, False, False, False, False, False, False, False, False]
1 2 ee [True, False, False, False, False, False, False, False, False]
0 2 lee [True, False, False, False, False, False, False, False, False]
-----loop-----
3 3 t [True, False, False, False, False, False, False, False, False]
2 3 et [True, False, False, False, False, False, False, False, False]
1 3 eet [True, False, False, False, False, False, False, False, False]
0 3 leet [True, False, False, False, False, False, False, False, False]
-----loop-----
4 4 c [True, False, False, False, True, False, False, False, False]
3 4 tc [True, False, False, False, True, False, False, False, False]
2 4 etc [True, False, False, False, True, False, False, False, False]
1 4 eetc [True, False, False, False, True, False, False, False, False]
0 4 leetc [True, False, False, False, True, False, False, False, False]
-----loop-----
5 5 o [True, False, False, False, True, False, False, False, False]
4 5 co [True, False, False, False, True, False, False, False, False]
3 5 tco [True, False, False, False, True, False, False, False, False]
2 5 etco [True, False, False, False, True, False, False, False, False]
1 5 eetco [True, False, False, False, True, False, False, False, False]
0 5 leetco [True, False, False, False, True, False, False, False, False]
-----loop-----
6 6 d [True, False, False, False, True, False, False, False, False]
5 6 od [True, False, False, False, True, False, False, False, False]
4 6 cod [True, False, False, False, True, False, False, False, False]
3 6 tcod [True, False, False, False, True, False, False, False, False]
2 6 etcod [True, False, False, False, True, False, False, False, False]
1 6 eetcod [True, False, False, False, True, False, False, False, False]
0 6 leetcod [True, False, False, False, True, False, False, False, False]
-----loop-----
7 7 e [True, False, False, False, True, False, False, False, False]
6 7 de [True, False, False, False, True, False, False, False, False]
5 7 ode [True, False, False, False, True, False, False, False, False]
4 7 code [True, False, False, False, True, False, False, False, False]
-----loop-----
Copy the code

As you can see, setting dp[0] to True is a split, and each True is a split point.

Word Break II

Subject to

Given a target string and a set of words, split the target string. The split part is required to be in that word group. The split words are separated by Spaces, giving all possible split cases.

Their thinking

Dynamic programming + depth-first reference: www.cnblogs.com/zuoyuan/p/3… This problem is not only to judge whether segmentation can be done like Word break, but also to find all segmentation methods, so we need to consider DFS.

But you can’t do it directly with DFS. Why? Because the decision tree is too large, the time complexity is too high to pass oJ if the whole tree is traversed once.

So we need to prune, how do we prune? Using the results of dynamic programming in word Break, before DFS, determine whether the string can be split, if not, directly skip this one. So this is actually dp plus DFS.

code

class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ Solution.res = [] self.dfs(s, wordDict, '') return Solution.res def dfs(self, s, wordDict, stringlist): If len(s) == 0: if len(s) == 0: Solution.res.append(stringlist[1:]) for i in range(1, len(s)+1): if s[:i] in wordDict: print stringlist+' '+s[:i] self.dfs(s[i:], wordDict, stringlist+' '+s[:i]) def check(self, s, wordDict): Dp = [False for I in range(len(s)+1)] dp[0] = True # for i in range(len(s)): for j in range(i, -1, -1): if dp[j] and s[j:i + 1] in wordDict: dp[i + 1] = True break return dp[len(s)]Copy the code

Output:

 cat
 cat sand
 cat sand dog
 cats
 cats and
 cats and dog
Copy the code

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign