给定一个字符串 s 和一个字符串数组 dic ,在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集(即拆分后的字符串集合中的所有字符串都在 dic 数组中),你可以以任意顺序 返回所有这些可能的拆分方案。
数据范围:字符串长度满足 ,数组长度满足 ,数组中字符串长度满足
"nowcoder",["now","coder","no","wcoder"]
["no wcoder","now coder"]
"nowcoder",["now","wcoder"]
[]
"nowcoder",["nowcoder"]
["nowcoder"]
"nownowcoder",["now","coder"]
["now now coder"]
你可以重复使用 dic 数组中的字符串
# -*- 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