M-139. Word Break

Loading...LeetCode

# O(n^2), O(n)
# BFS
from collections import deque
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDictSet = set(wordDict)
        queue = deque()
        visited = set()
        queue.append(0)
        
        while queue:
            start = queue.popleft()
            if start not in visited:
                for end in range(start, len(s)):
                    if s[start:end + 1] in wordDictSet:
                        queue.append(end + 1)
                        if end == len(s) - 1:
                            return True
                visited.add(start)
        return False