力扣139.单词拆分

?思路：动态规划，设dp[]记录当前字符能不能通过字典里的单词到达，双层循环，外层循环遍历字符串每一个字符，内层遍历当前i字符之前的所有以i字符结尾的子串

例如字符串：leetcode

i遍历到了t

那么内层循环就会遍历：leet、eet、et、t

然后判断这些子串中有没有与字典里的单词匹配，若匹配且当前dp[j]为真，则dp[i]为真

判断dp[j] 是因为若dp[j]为真，则代表j字符可以到达，那么当前字符子串以j为起始并且字典里存在此子串，所以当前子串的结尾处也可以到达（dp[i] = true）

dp[0] 赋初值true，因为若子串起始字符为第一个字符，那么从第一个字符出发的子串当然是可以的

最后判断dp[]最后一个位置是否为真，若为真则说明此字符串可以通过字典里的单词拼凑到达最后一个字符

一开始的笨办法，虽然笨且慢，不过可能更便于理解：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        auto dp = vector<bool> (len + 1);    
        dp[0] = true;    //dp[0]赋值

        for(int i = 1; i <= len; i++){     //外层循环遍历字符串
            int sw = true;    //开关，若内层循环确定当前字符可到达则进行下一个字符
            for(int j = 0; j < i && sw; j++){    //内层循环遍历i字符前每一个以i字符结尾的子串
                for(auto word:wordDict){    //在字典里面找有没有此子串
                    if(dp[j] && (word.compare(s.substr(j, i - j)) == 0)){    
                        dp[i] = true;    //如果子串存在可到达则i字符后一个字符也可到达
                        sw = false;    //如果当前字符可到达则无需继续遍历子串
                    }
                }
            }
        }

        return dp[len];
    }
};

加入unordered_set之后快了很多

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        auto dp = vector<bool> (len + 1);
        dp[0] = true;
        auto wordset = unordered_set <string> ();
        for(auto word : wordDict){
            wordset.insert(word);
        }

        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()){
                    dp[i] = true;
                    break;
                }

            }
        }

        return dp[len];
    }
};

思路不变，unordered_set就是一个key为值的字典，并且unordered_set中find()若找不到对应元素，会返回.end()