以下是一个示例代码,用于按照给定的单词列表拆分字符串:
def wordBreak(s, wordDict):
n = len(s)
# 创建一个数组来保存拆分结果
dp = [False] * (n + 1)
dp[0] = True # 空字符串可以被拆分
for i in range(1, n + 1):
for j in range(i):
# 如果前面的子字符串可以被拆分,并且后面的子字符串也在单词列表中,则更新dp[i]
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
# 如果最后一个元素为True,表示可以拆分成单词列表中的单词
if dp[n]:
# 使用dfs函数来获取所有可能的拆分结果
return dfs(s, wordDict, '', 0, [])
return []
def dfs(s, wordDict, path, start, res):
# 如果已经遍历到字符串末尾,将当前路径添加到结果中
if start == len(s):
res.append(path[:-1])
return
# 遍历从当前位置开始的所有子字符串
for i in range(start, len(s)):
# 如果子字符串在单词列表中,进行递归调用
if s[start:i+1] in wordDict:
dfs(s, wordDict, path + s[start:i+1] + ' ', i+1, res)
return res
# 测试示例
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
print(wordBreak(s, wordDict))
输出结果为:['cats and dog', 'cat sand dog']
上一篇:按照大量列的序数引用进行分组
下一篇:按照单词的值对数组进行排序