Word Break

Problem: Word Break

We can solve this problem by O(n^2) dynamic programming. Solution of string (i,j) is actually decided by (i,k) and whether (k,j) is in dictionary, while k is all numbers between i and j.

Code in Python:

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        n = len(s)
        dp = [True] + [False] * n
        for i in xrange(1, n+1):
            for j in xrange(0, i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]