🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

「算法」是面试「互联网大厂」必考题目，本篇文章就来解析一道大厂面试常见的题目。

一、题目描述

给定一个字符串 s 和一个字符串列表 wordDict 作为字典。请判断是否可以利用字典中出现的单词拼接出字符串 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

二、测试样例

2.1 样例一

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true，因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

2.2 样例二

输入: s = "leetcodeleet", wordDict = ["leet", "code"]

输出: true

解释: 返回 true，因为 "leetcodeleet" 可以由 "leet"、"code"、“leet” 拼接而成，“leet” 使用了两次。

三、算法思路

本题是典型的「钱币兑换」问题，用「完全背包」可以完美解决本题。

字符串 s 看做背包的容量，单词看做物品，单词是可以重复使用的，相当于物品可以重复使用。尝试用单词组装字符串 s，因为是正好组装成字符串 s，所以相当于判断物品是否能够正好装满背包。

dp[i] 表示字符串s[0, i] 是否能够正好通过单词拼装。那么，「状态转移方程」如下所示：

dp[i] = { dp[j] && wordDict.contains(s[j, i-1]) } （0 <= j < i） 

四、代码实现

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //将所有单词放入set集合中
        set<string> wordSet;
        for(auto word : wordDict) {
            wordSet.insert(word);
        }

        // 初始化 dp 数组
        bool dp[s.size()+1];
        // 全部初始化为 false
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        for(int i = 1; i <= s.size(); ++i) {
            for(int j = 0; j < i && !dp[i]; ++j) {
                dp[i] = dp[j] && wordSet.find(s.substr(j, i-j)) != wordSet.end();
            }
        }
        return dp[s.size()];
    }
};

int main()
{
    string str = "leetcode";
    vector<string> wordDict;
    wordDict.push_back("leet");
    wordDict.push_back("code");
    Solution obj;
    cout<<obj.wordBreak(str, wordDict)<<endl;
    return 0;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度为：O(n^2)，这里 n 指的是字符串 s 的长度，两层 for 循环，所以时间复杂度为 O(n^2)。

5.2 空间复杂度

空间复杂度为：O(n)，使用到了一个 dp 数组，长度为 n，使用到了一个 set 集合，综合后空间复杂度为 O(n)。

六、总结

本题首先需要理解题意，理解后转化为「完全背包」问题来解决。

🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞