单词拆分(二)

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param dic string字符串一维数组
# @return string字符串一维数组
#
class Solution:
    """
    题目：
        NC182 单词拆分(二)
        https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&&tqId=39349&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
        https://leetcode-cn.com/problems/word-break-ii/
    算法：
        记忆化搜索 回溯
        对于字符串s，如果某个前缀是单词表中的单词，然后对s剩余部分继续拆分。如果可以将整个字符串s拆分成单词列表中的单词，则可以得到1个句子。在对s的剩余部分拆分得到1个句子之后，将拆分出的第1个单词（即s的前缀）添加到句子的头部，即可得到1个完成的句子。上述过程可以通过回溯实现。
        使用哈希表存储字符串s的每个下标和该下标开始的部分可以组成的句子列表，在回溯过程中，如果遇到已经访问过的下标，则可以直接从哈希表得到结果，而不需要重复计算。如果到某个下标发现无法匹配，则哈希表中该下标对应的是空列表，因此可以对不能拆分的情况进行剪枝。
    复杂度：
        时间复杂度：O(n * 2^n)
        空间复杂度：O(n * 2^n)
    """

    def wordDiv(self, s, dic):
        # write code here
        def dfs(i):
            if i == n:
                return [[]]

            ans = []
            for j in range(i + 1, n + 1):
                word = s[i:j]
                if word in wordSet:
                    nextWordDivs = dfs(j)
                    for nextWordDiv in nextWordDivs:
                        ans.append(nextWordDiv[:] + [word])
            return ans

        n = len(s)
        wordSet = set(dic)
        divList = dfs(0)

        return [' '.join(words[::-1]) for words in divList]


if __name__ == '__main__':
    s = Solution()

    str, dic = "nowcoder", ["now", "coder", "no", "wcoder"]

    # str, dic = "nowcoder", ["now", "wcoder"]

    # str, dic = "nowcoder", ["nowcoder"]

    # str, dic = "aaaaaaaaaaaaaaaaaaaa", ["a", "aa", "aaa", "aaaa", "aaaaa",
    #                                     "aaaaaa", "aaaaaaa", "aaaaaaaa",
    #                                     "aaaaaaaaa", "aaaaaaaaaa"]

    res = s.wordDiv(str, dic)

    print res