题解 | 单词拆分(一)

#include <unordered_map>
class Solution {
public:
    // question: 数组子集，能否组成字符串
    // waht:用dp数组记录s[0]到s[i-1]能不能被组成
    // dp[i] = find(s[j-1]-s[i-1]) && dp[j-1];
    // why: 回溯，以数组为头遍历，凑一个，继续找下面的，不行就回溯；
    // 记忆就是，记录回溯，能否组成
    bool wordDiv(string s, vector<string>& dic) {
        vector<int> dp(s.size()+1, 0);  //能找到初始化,表示从0到i-1是否能被组成
        dp[0] =1;
        unordered_set<string> st;

        for(string elem:dic){
            st.insert(elem);
        }

        for(int i=1; i<=s.size(); i++){
            for(int j=i; j>=1; j--){
                if(st.count(s.substr(j-1, i-j+1))){  //数组中有子串
                    if(dp[j-1] == 1){
                        dp[i] = 1;
                        j = -1;
                        break;  //能组成，直接退出
                    }else{
                        dp[0] = 0;
                    }
                }
                else{
                    dp[i] = 0;
                }
            }
        }

        return dp.back();
    }
};