动态规划 – 单词拆分

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

1 暴力解法

按照题目的意思，字符串是由字符串列表拼接而成，故可以使用字符串列表去字符串中进行碰撞，如果全部的字符串列表都碰撞不到结果则返回false。

具体代码如下:

class Solution {
public:
    bool wordBreak(string s, vector& wordDict) {
        int start = 0, length = s.size();
        while(s.substr(start, length) != ""){
            int flag = 0;
            for(auto word:wordDict){
                if (word == s.substr(start, word.size())){
                    flag = 1;
                    start = start + word.size();
                    length = s.size() - start;
                }
            }
            if (!flag) return false;
        }
        return true;
    }
};

报错示例为：上述暴力做法为贪心思想，无法达到全局最优。cars->car，剩一个s无法被碰撞，返回false。实际上可以划分为[“ca”, “rs”]。

2 动态规划

从上述暴力做法中发现贪心暴力算法无法解决该问题，只能上动态规划算法了。