pylist

107. Word Break

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

Example 1:

	Input:  "lintcode", ["lint", "code"]
	Output:  true

Example 2:

	Input: "a", ["a"]
	Output:  true

Solution

from functools import lru_cache
class Solution:
    """
    @param: s: A string
    @param: dic: A set of words dict
    @return: A boolean
    """
    def wordBreak(self, s, dic):
        # nonsense
        if len(s) == 0:
            return True
        self.dic = dic
        return self.dfs(s)
        
    @lru_cache(None)
    def dfs(self, s):
        if s in self.dic:
            return True
        for i in range(1, len(s)+1):
            if s[0:i] in self.dic:
                return self.dfs(s[i:])
        return False

care