首页 > 试题广场 >

possible sentences

[编程题]possible sentences

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

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.

输入描述:

s ="catsanddog"
dict ="cat", "cats", "and", "sand", "dog"

输出描述:

[cats and dog, cat sand dog]

示例1

输入

s ="catsanddog"
dict ="cat","cats","and","sand","dog"

输出

[cats and dog, cat sand dog]

算法知识视频讲解

Python

ElonB

""""
深度优先搜索DFS
"""


def dfs(s, dic, arr, ans):
    if not s:
        ans.append(' '.join(arr))
    for w in dic:
        if s.startswith(w):
            dfs(s[len(w):], dic, arr + (w,), ans)


if __name__ == "__main__":
    s = input().strip()
    s = s[s.index('"') + 1:-1]
    dic = input().strip()
    dic = eval("[" + dic[dic.index('"'):] + "]")
    dic.sort(reverse=True)
    ans = []
    dfs(s, dic, tuple(), ans)
    print('[' + ', '.join(ans) + ']')

发表于 2019-07-16 14:06:25 回复(0)