首页 > 试题广场 >

单词拆分(二)

[编程题]单词拆分(二)

热度指数：1637 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序返回所有这些可能的拆分方案。

数据范围：字符串长度满足 $1 \le n \le 20 \$ ，数组长度满足 $1 \le n \le 10 \$ ，数组中字符串长度满足 $1 \le n \le 20 \$

示例1

输入

"nowcoder",["now","coder","no","wcoder"]

输出

["no wcoder","now coder"]

示例2

输入

"nowcoder",["now","wcoder"]

输出

[]

示例3

输入

"nowcoder",["nowcoder"]

输出

["nowcoder"]

示例4

输入

"nownowcoder",["now","coder"]

输出

["now now coder"]

说明

你可以重复使用 dic 数组中的字符串

算法知识视频讲解

Python 3

Density666

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

发表于 2022-08-15 05:35:01 回复(0)