XTAO's Tech Blog
0%

[Leetcode]140. Word Break II(C++)

发表于 更新于 分类于 ， 评论数：
2.8k 3 分钟

题目描述

题目链接：140. Word Break II

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. Return all such possible sentences.

例子

例子 1

Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]

例子 2

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

例子 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: []

Note

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

解题思路

这种要求输出所有可能的组合（这道题是句子）通常都需要用回溯法进行暴力遍历获取所有组合并从中挑出符合要求的结果。由于回溯法的时间复杂度通常比较高，所以通过条件进行一定程度上的剪枝。这道题中回溯的具体做法如下：

  • 首先用哈希表存储字典中的单词
  • 对字符串进行递归遍历，递归过程传入一个索引作为遍历的起始位置，一个字符串作为当前句子
  • 首先初始化当前单词为空，在遍历过程，我们不断扩充当前单词，当发现当前单词在字典中（哈系表常数时间查询），进行以下操作：
    • 将当前单词加入当前句子中（如果不是第一个单词的话还需要加一个空格）
    • 递归调用函数，传入下一个索引的位置以及更新后的句子
    • 遍历完成后我们需要重置句子为原先状态以便继续遍历并重新加入单词，因此根据当前单词的长度去除句子末尾的元素
    • 继续遍历下一位置扩充单词进行重复操作

除此之外，在遍历之前我们可以通过判断字符串是否只包含字典中单词的字母，如果不满足该条件可以直接返回空集。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <string>
#include <unordered_set>
#include <vector>

class Solution {
public:
    std::vector<std::string> wordBreak(std::string s,
                                       std::vector<std::string>& wordDict) {
        std::vector<bool> letter_count(26, false);

        for (const auto& word : wordDict) {
            m_dict.insert(word);
            for (char c : word) {
                letter_count[c - 'a'] = true;
            }
        }

        // check s only contains letters in dict first
        for (char c : s) {
            if (!letter_count[c - 'a']) return {};
        }

        std::string current_sentence;
        findWords(s, 0, current_sentence);
        return m_result;
    }

private:
    std::unordered_set<std::string> m_dict;
    std::vector<std::string> m_result;

    void findWords(const std::string& s, int idx,
                   std::string& current_sentence) {
        if (idx == s.length()) {
            m_result.push_back(current_sentence);
            return;
        }

        std::string current_word = "";
        for (int i = idx; i < s.length(); i++) {
            // expand word
            current_word += s[i];
            // use it as seperate word and find next word
            if (m_dict.count(current_word) != 0) {
                if (idx != 0) current_sentence += " ";
                current_sentence += current_word;
                findWords(s, i + 1, current_sentence);
                if (idx != 0) {
                    current_sentence.erase(current_sentence.length() -
                                           current_word.length() - 1);
                } else {
                    current_sentence = "";
                }
            }
        }
    }
};
  • 时间复杂度: O(2^n)
  • 空间复杂度: O(2^n)

GitHub 代码同步地址： 140.WordBreakIi.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章