LeetCode: 139. Word Break

题目描述

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.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

题目大意： 判断给定字符串 s 是否能由给定的单词表 wordDict 中的单词拼凑出。

解题思路 —— 动态规划

1. 描述最优解的结构。记 frontWordBreak[i] 为 s 串是否能够由 wordDict 中的字符串拼凑成。
2. 递归地定义最优解的值。如果 s 串在 [i, j) 区间的子串能在 wordDict 中找到，则 frontWordBreak[j] 的值取决于 frontWordBreak[i] 的值。 状态转移方程如下图：
   

3. 自底向上计算最优解的值

   For i From 1 To s.size Do For j From 0 To wordDict.size - 1 Do If s[i-wordDict[j].size...wordDict[j].size] = wordDict[j] frontWordBreak[i] := (frontWordBreak[i] || i-wordDict[j].size)；

4. 例子。下表是对 Example 1 进行的分析。每一行代表 frontWordBreak 在某个时间的状态。

   

AC 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // frontWordBreak[i]: s 串的前 i 个字符是否能在 wordDict 中拼凑出
        vector<bool> frontWordBreak(s.size() + 1, false); 

        //初始化：定义空串能被 wordDict 拼凑出
        frontWordBreak[0] = true;

        for(size_t i = 1; i <= s.size(); ++i)
        {
            for(size_t j = 0; j < wordDict.size(); ++j)
            {
                if(wordDict[j].size() > i) continue;

                // 自底向上计算最优解的值
                if(s.substr(i-wordDict[j].size(), wordDict[j].size()) == wordDict[j] 
                    && !frontWordBreak[i])
                {
                    frontWordBreak[i] = frontWordBreak[i-wordDict[j].size()];
                }
            }
        }

        return frontWordBreak.back();
    }
};