Word Break

• Lintcode : 107 / Leetcode : 139
• Level : Medium
• Follow up : Word Break II, Word Break III

Problem

Given a string s and a dictionary of words dict, determine if s can be broken into a space-separated sequence of one or more dictionary words.

Example
Example 1:
    Input:  "lintcode", ["lint", "code"]
    Output:  true

Example 2:
    Input: "a", ["a"]
    Output:  true

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n ^ 2) Worst Case
space: O(n)

Answer

class Solution {
public:
    bool wordBreak(string &s, unordered_set<string> &dict) {
        vector<int> index;
        int n = s.length();
        // corner case
        if (n == 0) return true;
        int maxLength = INT_MIN;
        for (auto i : dict) {
            maxLength = max(maxLength, static_cast<int> (i.length()));
        }
        vector<bool> dp(n, false);
        for (int i = 0; i < n; i++) {
            string str = s.substr(0, i + 1);
            if (dict.find(str) != dict.end()) {
                dp[i] = true;
                index.push_back(i);
            }else {
                for (int j = index.size() - 1; j >= 0; j--) {
                    if (i - index[j] > maxLength) break; 
                    string temp = s.substr(index[j] + 1, i - index[j]);
                    if (dict.find(temp) != dict.end()) {
                        dp[i] = true;
                        index.push_back(i);
                        break;
                    }
                }
            }
        }
        return dp[n - 1];
    }
};

tags: DP

​