lintcode-107-单词切分

107-单词切分

思路

使用动态规划，用一维数组 dp[i] 保存 0 - i 的子串可以被空格切分成一个或多个出现在字典中的单词

code

class Solution {

public:

    /*

     * @param s: A string

     * @param dict: A dictionary of words dict

     * @return: A boolean

     */

    bool wordBreak(string s, unordered_set<string> dict) {

        // write your code here

        int sizeS = s.size(), sizeD = dict.size();

        if (sizeS == 0 && sizeD == 0) {

            return true;

        }

        if (sizeS == 0 || sizeD == 0) {

            return false;

        }

        vector<bool> dp(sizeS + 1, false);

        dp[0] = true;

        for (int i = 0; i < sizeS; i++) {

            for (string str : dict ) {

                if (dp[i] == true && i + str.size() <= sizeS && s.substr(i, str.size()) == str) {

                    dp[i + str.size()] = true;

                }

            }

        }

        return dp[sizeS];

    }

};