Press "Enter" to skip to content

花花酱 Leetcode 140. Word Break II

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
微信打赏

4 Comments

  1. chch1 chch1 March 23, 2018

    花花前辈,请问下这个题目的时间复杂度和空间复杂度,谢谢:)

    • zxi 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 joeykou June 9, 2018

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

        • zxi zxi Post author | June 15, 2018

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

Leave a Reply