单词拆分(二)

class Solution:
    def wordDiv(self , s: str, dic: List[str]) -> List[str]:
        # write code here
        res = []
        path = []
        index = 0
        
        def backtrack(index):
            if index >= len(s):
                res.append(' '.join(path[:]))
                return 
            for i in range(index, len(s)):
                p = s[index : i + 1]
                if p in dic:
                    path.append(p)
                else:
                    continue 
                backtrack(i + 1)
                path.pop()
        
        backtrack(index)
        return res

# -*- 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

static Set<String> list=new HashSet<>();
    
    public String[] wordDiv (String s, String[] dic) {
        StringBuilder st=new StringBuilder();
        findWord(st,s,dic);
        String[] sa=new String[list.size()];
        list.toArray(sa);
        return sa;
    }
    
    void findWord(StringBuilder ss, String sc, String[] dic){
        if(sc.length()==0){
            ss.delete(ss.length()-1,ss.length());
            list.add(ss.toString());
            ss.append(" ");
            return;
        }
        for(int i=0;i<dic.length;i++){
            if(dic[i].length()<=sc.length()&&sc.substring(0,dic[i].length()).equals(dic[i]))
            {
                ss.append(dic[i]+" ");
                findWord(ss,sc.substring(dic[i].length()),dic);
                ss.delete(ss.length()-dic[i].length()-1,ss.length());
            }
        }
    }