139_word_break.py

'''
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can 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.
'''
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordDict = set(wordDict)
        hash_table = [False for _ in xrange(len(s)+1)]
        hash_table[-1] = True
        for i in xrange(len(s)-1, -1, -1):
            for j in xrange(i+1, len(s)+1):
                if hash_table[j] and s[i:j] in wordDict:
                    hash_table[i] = True
        # print hash_table
        return hash_table[0]

s = Solution()
assert s.wordBreak("leetcode", ["leet", "code"])