Word Break解题报告

Description:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

Example:

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Link:

https://leetcode.com/problems/word-break/#/description

解题方法：

用DP做。
假设dp[i]表示从字符串S从0~i-1的子串能被word break掉。状态转移方程为：
dp[i] = dp[j] && wordDict中能找到substr(j, i-j)
最前面dp[0]先初始化为true。

Tips:

在创建哈希表的时候把wordDict中最长的string长度记下来，如果i-j > 这个长度，则后面的子串可以不用检查。

Time Complexity：

时间：O(N^2)
空间：O(M)

完整代码：

bool wordBreak(string s, vector<string>& wordDict) 
    {
        if(s.size() == 0 || wordDict.size() == 0)
            return false;
        unordered_set<string> hash;
        int maxLen = 0;
        for(string str: wordDict)
        {
            maxLen = str.size() > maxLen ? str.size() : maxLen;
            hash.insert(str);
        }
        vector<bool> dp(s.size(), false);
        dp[0] = true;
        for(int i = 1; i <= dp.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(!dp[j] || i - j > maxLen)
                    continue;
                string temp = s.substr(j, i-j);
                if(hash.find(temp) != hash.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }