139. Word Break

"""
139. Word Break
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.

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

思路：
这道题要我们找出并非一种可能的词语拆分，比如例子里面的 “applepenapple” 是由 apple * 2 + pen * 1 组成的。
所以第一个直接的想法就是backtrack，就从头开始brute force地去遍历每一个字母看看是不是在wordDict里面。如果在dict里面，那么就recursive地遍历后面的string。但是这种办法会产生OJ不让过，所以我们要用到一个memo的list去纪录每一步计算过的结果。
解法如下：
1）首先要把wordDict的list type 转换成 set type 这么做是因为我们要检查当前的string是否在wordDict中，x in list is O(n) 而 x in set is O(1)
2) 然后产生一个memo来记录我们计算过的位置 [-1] * len(str)
3) backtack 从index = 0 开始， 每一层递归中依次遍历到string的末尾， 如果当前遍历到的string在wordDict中，并且剩余的string也从recursive中返回为1那么就说明从index位开始到string的末尾，都能在wordDict中找到，然后修改memo[idx] = 1。如果在当前递归层中string遍历到末尾了都没有找到wordDict的值那就说明从index开始，不能再wordDict中找到，修改memo[idx] = 0
"""

class Solution(object):
    def backtrack(self, s, idx, st, memo):
        if idx == len(s):
            return 1

        if memo[idx] != -1:
            return memo[idx]

        for i in range( idx+1, len(s)+1 ):
            if s[idx:i] in st and self.backtrack(s, i, st, memo):
                memo[idx] = 1
                return memo[idx]

        memo[idx] = 0
        return memo[idx]

    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        st = set(wordDict)
        memo = [-1] * len(s)
        res = self.backtrack(s, 0, st, memo)
        return True if res is 1 else False