欢迎访问LeetCode题解合集

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

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

题解：

法一：

记忆化搜索。

参考 分割回文串 一题思路，递归过程中维护单词的起始位置，枚举所有可能的结束位置。

注意：只是单纯的爆搜，会出现大量的重复状态，所以使用记忆化搜索优化。

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

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

class Solution {
public:
    unordered_set<string> hash;
    vector<int> f;
    bool dfs( int st, const string& s ) {
        if ( st >= s.size() ) return true;
        if ( f[st] != -1 ) return f[st];
        string t;
        for ( int i = st; i < s.size(); ++i ) {
            t = s.substr( st, i - st + 1 );
            if ( !hash.count( t ) ) continue;
            if ( dfs( i + 1, s ) ) return f[st] = true;
        }
        return f[st] = false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        for ( const auto& it : wordDict )
            hash.insert( move(it) );
        f = vector<int>( s.size(), -1 );
        return dfs( 0, s );
    }
};
/*
时间：20ms，击败：55.74%
内存：13.1MB，击败：41.65%
*/

法二：

动态规划。

设 f[i] 表示 s 的前 i 个字符能否由 wordDict 组成，其中 f[0] = true 。那么若 f[i] = true 且 s[i+1...j] 在 wordDict 中，那么 f[j] = true 。

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

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

class Solution {
public:

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