https://leetcode.com/problems/word-break/description/

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. You may assume the dictionary does not contain duplicate words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

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

---

• 中等题，动态规划。
• 定义 F[i] stands for s[0...i-1] is a valid sequence，那么F[i] = F[j] && find(s[j...i-1])，其中F[0] = true; 0 <= j < i; 0 <= i <= s.size(); 最终结果为F[s.size()]。
• find - C++ Reference
  • http://www.cplusplus.com/reference/algorithm/find/?kw=find
• 根据C++ Primer，使用关联容器定义的专用的find成员会比调用泛型find快得多。所以如果是map，则用map::find()更快。
  • map::find - C++ Reference
    • http://www.cplusplus.com/reference/map/map/find/

////  main.cpp//  LeetCode////  Created by Hao on 2017/3/16.//  Copyright © 2017年 Hao. All rights reserved.//////  main.cpp//  LeetCode////  Created by Hao on 2017/3/16.//  Copyright © 2017年 Hao. All rights reserved.//#include 
      
       #include 
       
        using namespace std;class Solution {public:    bool wordBreak(string s, vector
        
         & wordDict) {        vector
         
              f(s.size() + 1, false);                /*         F[i] stands for s[0...i-1] is a valid sequence         F[0] = true;         F[i] = F[j] && find(s[j...i-1])         0 <= j < i         0 <= i <= s.size()         */        f[0] = true;    // empty string        for (int i = 1; i < s.size() + 1; i ++)            for (int j = 0; j < i; j ++)                if (f[j] && find( wordDict.begin(), wordDict.end(), s.substr( j, i - j ) ) != wordDict.end() ) {                    f[i] = true;                    break;                }                return f[s.size()];    }};int main(){    Solution        testSolution;    string          inputS = "leetcode";    vector
          
             inputWD = {
    "leet","code"};        /*     1     */    cout << testSolution.wordBreak(inputS, inputWD) << endl;        return 0;}