Word Break

Question

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Tags

• DFS
• Dynamic Programming

Thoughts

There are two ways to solve the problem: DFS or Dynamic Programming.

1. DFS

DFS need to divide the string into two substrings in and keep dividing until the substring is in the set of wordDict. This is a easy solution for implementation. However, for a large wordDict and long string, the time complexity will be O(n^2), which is not acceptable for OA.

1. Dynamic Programming

The reason of the huge computation cost for DFS is the repeated calculation during the search. Thus, it is a reasonable solution to use the Dynamic Programming algorithm to avoid the repeated calculation and decrease the time complexity.

Here, the DP table is an array which has equal length to the string. The item at the ith position in the table represents whether the substring of the previous i characters in the string can be broken into words.

DP[i] = 0: not calculated yet
DP[i] = -1: cannot be broken into words
DP[i] = 1: can be broken into words

Code

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """

        DP = [0 for i in xrange(len(s))]
        if s[0] in wordDict:
            DP[0] = 1
        else:
            DP[0] = -1

        for i in xrange(1, len(s)):
            index = i + 1
            word = s[:index]
            if word in wordDict:
                DP[i] = 1
            else:
                for j in xrange(len(word) - 1):
                    if DP[j] == -1:
                        continue
                    else:
                        if word[j + 1:] in wordDict:
                            DP[i] = 1
                            break
                if DP[i] == 0:
                    DP[i] = -1


        if DP[-1] == -1:
            return False
        else:
            return True