[Python] 46ms bottom-up DP and DFS.


  • 1
    O
    class Solution(object):
    
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: List[str]
            """
            res = []
            length = len(s)
            # DP[j]:表示[j:length)能否切分,使得子串能够被包含在worddict中。
            DP = [False] * (length + 1)
            DP[length] = True
            # bottom to up
            for j in range(length, -1, -1):
                for i in range(j - 1, -1, -1):
                    if DP[j] and (s[i: j] in wordDict):
                        DP[i] = True
    
            def DFS(index, valueList):
                # cut
                if DP[index]:  # 从下标Index开始,划分子串,能够满足题目条件,就进行递归
                    if index == length:
                        res.append(valueList[1:])
                        return
    
                    #记得这边是length+1,i能够达到的最大的是length,在切片的时候[index:i],最终只能访问到i-1,最大就是length-1.
                    for i in range(index + 1, length + 1): 
                        if s[index:i] in wordDict and DP[i]:
                            DFS(i, valueList + " " + s[index : i])
    
            DFS(0, "")
            return res
    

  • 0
    E

    Hi,

    Thanks for sharing this amazing code.

    Your DFS part was quite neat, and I got that part. Yet the first part to get DP why did you go through the string from right to left?
    I have my own DP list, but mine was going from the left to right. DP[j] will be if s[0:j] can be cut.

    Yours worked well, but my method had a TLE. I was very curious of the difference. Thanks!


  • 0
    O

    Sorry, I have seen your problem right now. I have wrote down the code follow your idea and AC. However, I find that the run time is not very good compare to from bottom to up.

    class Solution(object):
    
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: List[str]
            """
            res = []
            length = len(s)
            # DP[j]:表示[0 : j)能否切分,使得子串能够被包含在worddict中。
            DP = [False] * (length + 1)
            DP[0] = True
    
            for j in range(0, length + 1):
                for i in range(j + 1, length + 1):
                    if DP[j] and (s[j : i] in wordDict):
                        DP[i] = True
    
            def DFS(index, valueList):
                # cut
                if DP[index]:  # 从下标Index开始,划分子串,能够满足题目条件,就进行递归
                    if index == 0:
                        res.append(valueList[:-1])
                        return
    
                    #记得这边是length+1,i能够达到的最大的是length,在切片的时候[index:i],最终只能访问到i-1,最大就是length-1.
                    for i in range(index - 1, -1, -1): 
                        if s[i : index] in wordDict and DP[i]:
                            DFS(i, s[i : index] + " " + valueList)
    
            DFS(length, "")
            return res
    

Log in to reply
 

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