欢迎访问LeetCode题解合集

题目描述：

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

题解：

法一：

回溯 + 记忆化搜索。

参考 单词拆分 方法一，在这题基础上保存结果，回溯即可。

时间复杂度：$O(n * 2^n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    unordered_set<string> hash;
    vector<string> path;
    vector<string> ret;
    vector<int> f;
    bool dfs( int st, const string& s ) {
        if ( st >= s.size() ) {
            string t = "";
            for ( int i = 0; i < path.size(); ++i ) {
                if ( i ) t += ' ';
                t += path[i];
            }
            ret.emplace_back( move(t) );
            return true;
        }
        if ( !f[st] ) return f[st];
        string t;
        bool flag = false;
        for ( int i = st; i < s.size(); ++i ) {
            t = s.substr( st, i - st + 1 );
            if ( !hash.count(t) ) continue;
            path.emplace_back( move(t) );
            flag |= dfs( i + 1, s );
            path.pop_back();
        }
        return f[st] = flag;
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        f = vector<int>( s.size(), -1 );
        for ( const string& it : wordDict )
            hash.insert( move(it) );
        dfs( 0, s );
        return ret;
    }
};
/*
时间：16ms，击败：78.29%
内存：12.3MB，击败：59.44%
*/

法二：

回溯 + 动态规划。

参考 单词拆分 方法二，动态规划完成后，根据 f 的状态进行回溯搜索所有结果。

时间复杂度：$O(n * 2^n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    unordered_set<string> hash;
    vector<string> path;
    vector<string> ret;
    vector<bool> f;

    void dfs( int st, const string& s ) {
        if ( st >= s.size() ) {
            string t = "";
            for ( int i = 0; i < path.size(); ++i ) {
                if ( i ) t += ' ';
                t += path[i];
            }
            ret.emplace_back( move(t) );
            return;
        }
        string t;
        for ( int i = st + 1; i <= s.size(); ++i ) {
            if ( !f[i] ) continue;
            t = s.substr( st, i - st );
            if ( !hash.count(t) ) continue;
            path.emplace_back( move(t) );
            dfs( i, s );
            path.pop_back();
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for ( const string& it : wordDict )
            hash.insert( move(it) );
        f = vector<bool>( s.size() + 1 );
        f[0] = true;
        int size;
        for ( int i = 0; i < s.size(); ++i ) {
            if ( !f[i] ) continue;
            for ( const string& it : wordDict ) {
                size = it.size();
                if ( i + size <= s.size() && s.substr(i, size) == it )
                    f[i + size] = true;
            }
        }
        if ( !f[s.size()] ) return ret;
        dfs( 0, s );
        return ret;
    }
};
/*
时间：4ms，击败：99.25%
内存：8.6MB，击败：96.34%
*/