# Python BFS beats 95%

• 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
``````

• 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``````

• @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.

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