139. word break

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

        if s == '':
            return True
        checklist = [False]*(len(s)+1)
        checklist[len(s)] = True
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i:j+1] in wordDict and checklist[j+1]==True:
                    checklist[i]=True
        return checklist[0]

if __name__ == "__main__":
    answer = Solution()
    print answer.wordBreak("bb",["a","b","bbb","bbbb"])