leetcode139 单词拆分

题目

分析

使用hash表来存字典，然后对字符串s判断(i,j)位置间的字符串是否存在与字典中，存在的话，再判断(0,i-1)位置的字符串是否在字典中。
时间复杂度:O(n*n)。空间复杂度:O(n + m)。

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& words) {

        set<string> st(words.begin(), words.end());

        int len = s.size();
        vector<int> dp(len, 0);

        for (int i = 0; i < len; i++){
            for (int l = 1; i + l - 1 < len; l++){

                int j = i + l - 1;

                string str = s.substr(i, l);

                if (st.count(str) != 0 && (i - 1 >= 0 && dp[i - 1] == 1 || i == 0)){           
                    dp[j] = 1;
                }
            }
        }

        return dp[len - 1] == 1 ? true : false;
    }
};