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