Python BFS beats 95%


  • 3

    I use BFS to avoid useless states calculation like someone did in Coin Change. I do not check every substring but I check the substring whose length is possible (I store all distinct length of words in a list). Thus, no need to check backward from the current position one by one.

    It runs for 44ms in average while my original DP is 58ms.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: bool
            """
            queue = [0]
            slen = len(s)
            lenList = [l for l in set(map(len,wordDict))]
            visited = [0 for _ in range(0, slen + 1)]
            while queue:
                tmpqueue = []
                for start in queue:
                    for l in lenList:
                        if s[start:start+l] in wordDict:
                            if start + l == slen:
                                return True
                            if visited[start + l] == 0:
                                tmpqueue.append(start+l)
                                visited[start + l] = 1
                queue, tmpqueue = tmpqueue, []
            return False
    

  • 0
    S

    Nice solution. Your solution is a BFS search based on queue.

    Here is my implementation based on your code. I remove some useless code.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: bool
            """
            queue = [0]
            ls = len(s)
            lenList = [l for l in set(map(len, wordDict))]
            visited = [0 for _ in range(0, ls + 1)]
            while queue:
                start = queue.pop(0)
                for l in lenList:
                    if s[start:start + l] in wordDict:
                        if start + l == ls:
                            return True
                        if visited[start + l] == 0:
                            queue.append(start + l)
                            visited[start + l] = 1
            return False

  • 0

    @sloth Now I remove the usuless line of code in my post, thanks.

    In your code, queue.pop(0) is a O(n) operation which could make your implementation slower.


Log in to reply
 

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