[LeetCode 139] Word Break

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

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

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

Diffculty
Medium

Similar Problems
[LeetCode ] Linked List Cycle Easy [LeetCode ] Find the Duplicate Number Hard

Analysis

这类单词搜索的题，第一反应是 DFS 枚举的方式进行回溯查找，但题目并不要求给出是如何 break 的，而只要判断是否能 break。对这类判断“是”与“否”的可以用 DFS 暴力解决的题，可以尝试用 DP 做 book keeping 中间判断状态，避免 DFS 的反复回溯搜索。比如这题，可以用一个数组 dp 记录 S[0:i] 是否能 break。

dp[i] 标识位置 i 之前的序列能否 break。也即 S[0:i-1] 是否能被 break。例如 dp[1] 表示 s[0:0] 是否能被 break。

（1）初始值 dp[0] = true （2）状态转换方程：dp[i] = true if and only if:

• (i) 存在一个 k ∈ [0, i-1] ，使位置 k 后面部分的字串 s[k:i-1] 存在于给定的 dict 数组中。
• (ii) s[0: k-1] 可以 break，即 dp[k] = true。

注意：虽然 dp[1] 可以直接确定为 true，但是可以由 dp[0] 得来（即满足 dp[j] && dict.count(s.substr(j, i - j + 1)) != 0 条件）

Solutions

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        for (int i = 0; i < s.size(); i++) {     // 遍历每个元素 i
            for (int j = i; j >= 0; j--) {       // 考虑 0 - i 部分的元素
                if (dp[j] && dict.count(s.substr(j, i - j + 1)) != 0) { // 如果前半部分可以 break，并且后半部分也是一个完整单词
                    dp[i + 1] = true;            // found, break out
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};