LeetCode 139. Word Break

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 <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool>    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<string>  inputWD = {"leet","code"};
    
    /*
     1
     */
    cout << testSolution.wordBreak(inputS, inputWD) << endl;
    
    return 0;
}