139.Word Break

Tags: [dp], [top_to_bottom], [memo], [recursion]

Com: {fb}

Link: https://leetcode.com/problems/word-break/\#/description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if scan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s="leetcode",
dict=["leet", "code"].

Return true because"leetcode"can be segmented as"leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution: DP, Top To Bottom DP, Recursion

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return True
        if not wordDict:
            return False

        memo = [None for _ in xrange(len(s))]
        return self.word_break_helper(s, 0, set(wordDict), memo)

    def word_break_helper(self, s, index, word_dict, memo):
        # base case.
        if index >= len(s):
            return True

        if memo[index] is not None:
            return memo[index]

        for i in xrange(index, len(s)):
            curr = s[index:i + 1]
            if curr in word_dict and self.word_break_helper(s, i + 1, word_dict, memo):
                memo[index] = True
                return True

        memo[index] = False
        return False

Note:

• Time complexity = O(n), n is the length of the given s. Because each cell of memo just be filled once.