Word Break III

• Lintcode : 683 / Leetcode :
• Level : Medium

Problem

Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example
Example1

Input:
"CatMat"
["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
Output: 3
Explanation:
we can form 3 sentences, as follows:
"CatMat" = "Cat" + "Mat"
"CatMat" = "Ca" + "tM" + "at"
"CatMat" = "C" + "at" + "Mat"
Example1

Input:
"a"
[]
Output: 0
Notice
Ignore case

Concept & Algorithm

先用transform將dict & s都變成lowercase
因為ignore cases

Solution DP
int n = s.size()
1. 創建一個dp(n + 1, 0)
dp[i]用來存儲能夠構成前i個字串的方法數
2. 兩個for loop，
外圈 i (i = 1 ~ n) / 內圈 j (j = 0 ~ i - 1)

for (int i = 1; i <= s.size(); i++) {
    // 先確認前i個全字串是否存在，是的話dp[i] = 1
    dp[i] = hs.count(s.substr(0, i)) ? 1 : 0;
    // 接下來拆分字串
    // ex: abc 
    // 1. j = 0, i - j = 3 temp = abc
    // dp[i] += dp[0]
    // 2. j = 1, i - j = 2 temp =bc
    // dp[i] += dp[1] (a), 只要bc存在，把bc拿出來看看組成a的方法有幾種，因為只要組成a的方法有幾種，就代表a + bc的組成方法
    // 3. j = 2, i - j = 1 temp =c
    // dp[i] += dp[2] (ab), 只要c存在，把c拿出來看看組成ab的方法有幾種，因為只要組成ab的方法有幾種，就代表ab + c的組成方法
    for (int j = 0; j < i; j++) {
        string temp = s.substr(j, i - j);
        if (hs.count(temp)) {
            dp[i] += dp[j];
        }
    }
}
3. 最後 return dp[n]

Solution Memoization
1. 創建 unordered_map<string, int> repeat
用來記錄組成該string的方法數int
2. 進入dfs(string s, unordered_set<string>& dict, unordered_map<string, int> &repeat)
    a. 結束條件是當s為空的時候 return 1
    代表一種方法成立了
    b. 假設先前出現過該s，就可以直接知道方法數
    if (repeat.find(s) != repeat.end()) 
            return repeat[s];
    c. str由(i = 1 ~ n)也就是從前1個到全部完整
       然後確認拆分後，是否存在dict，若存在，剩下的就繼續dfs
       ex: abc, i = 1, a + bc, a存在的話bc繼續
       times += 會將組成bc的方法數目傳回來加總
       然後再換 abc, i = 2, ab + c, ab存在的話c繼續
       times += 會將組成c的方法數目傳回來加總
       然後再換 abc, i = 3, abc + "", abc存在的話""繼續
       times += 會將組成""的方法數目傳回來加總
    int times = 0;
    for (int i = 1; i <= s.size(); i++) {
        string str = s.substr(0, i);
        if (dict.find(str) == dict.end()) continue;
        times += dfs(s.substr(i), dict, repeat);
    }
    d. 加總完後出了循環，repeat[abc] = times，最後回傳給上一層times
       repeat[s] = times;
       return times;

Time Complexity & Space Complexity

dp

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

Memoization

time : O((2 ^ n) - 1)
space: O(n)

Answer

class Solution {
public:
    int wordBreak3(string& s, unordered_set<string>& dict) {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        unordered_set<string> hs;
        for (auto row : dict) {
            transform(row.begin(), row.end(), row.begin(), ::tolower);
            hs.insert(row);
        }
        vector<int> dp(s.size() + 1, 0);
        for (int i = 1; i <= s.size(); i++) {
            dp[i] = hs.count(s.substr(0, i)) ? 1 : 0;
            for (int j = 0; j < i; j++) {
                string temp = s.substr(j, i -j);
                if (hs.count(temp)) {
                    dp[i] += dp[j];
                }
            }
        }
        // return dp[s.size()];
        unordered_map<string, int> repeat;
        return dfs(s, hs, repeat);

    }
private:
    int dfs(string s, unordered_set<string>& dict, unordered_map<string, int> &repeat) {
        if (s.empty()) return 1;
        if (repeat.find(s) != repeat.end()) 
            return repeat[s];

        int times = 0;
        for (int i = 1; i <= s.size(); i++) {
            string str = s.substr(0, i);
            if (dict.find(str) == dict.end()) continue;
            times += dfs(s.substr(i), dict, repeat);
        }
        repeat[s] = times;
        return times;
    }
};

tags: DP

​