# Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

# Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

Python3

# Related Problems

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode

1. chch1 March 23, 2018

花花前辈，请问下这个题目的时间复杂度和空间复杂度，谢谢：）

• zxi Post author | March 24, 2018

时间复杂度和空间复杂度都是O(2^n)

T(n) = T(0) + T(1) + … + T(n – 1) = O(2^n)

input = “abcde” dict=[“a”, “b”, “c”, “d”, “e”, “bc”, “bcd”, “bcde”, “cd”, “cde”, “de”]

“abcde”

“a bcde”
“a b cde”
“a b c de”
“a b cd e”
“a b c d e”
“a bc de”
“a bc d e”
“a bcd e”

“ab cde”
“ab c de”
“ab cd e”
“ab c d e”

“abc de”
“abc d e”

“abcd e”

• joeykou June 9, 2018

你好，我有一个疑问，为什么这个空间复杂度没有考虑递归stack所占用的空间呢？ 谢谢

• zxi Post author | June 15, 2018

stack所占空间应该是O(n)，不在一个数量级上面，所以可以不用考虑。