博文中会简要介绍Leetcode P0139题目分析及解题思路。

“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.

一维费用背包问题属于比较经典的动态规划问题。在这里s的长度可以看作背包的容量，wordDict中每个单词的长度可以看作物品的费用。与背包问题的差异在于，这个问题只需要知道是否存在一种选取方法，使得wordDict中选取的词能够拼接并且恰好和s相等。这道题的递推表达式如下，

令dp[i]表示s[0:i-1]能否由wordDict中的词拼接而成，

dp[0] = true,
显然长度为0时可以由0个单词拼接而成，

dp[i] = dp[i] || (dp[i-L] && word == s.substring(i-L, i), L = word.length() for every word in wordDict,
对于wordDict中的每个单词，当i的长度大于该单词，我们关注s[i-L:i-1]的子串是否和当前相等，且前缀是否能够被拼接。以上任意一个条件不满足，则为false。

以下是Java的题解代码实现。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
        int N = s.length();
        boolean[] dp = new boolean[N+1];
        dp[0] = true;
        
        for (int i1=1; i1<=N; ++i1) {
            for (String word: wordDict) {
                int L = word.length();
                if (i1-L < 0)
                    continue;
                
                String segment = s.substring(i1-L, i1);
                dp[i1] = dp[i1] || (dp[i1-L] && word.equals(segment));
            }
        }
        
        return dp[N];
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int N = s.length();
        bool *dp = new bool[N+1];
        dp[0] = true;
        
        for (int i1=1; i1<=N; ++i1) {
            dp[i1] = false;
            for (string word: wordDict) {
                int L = word.length();
                if (i1 < L)
                    continue;
                
                string segment = s.substr(i1-L, L);
                dp[i1] = dp[i1] || (dp[i1-L] && segment == word);
            }
        }
        
        return dp[N];
    }
};