Word Break I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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".

代码：

 class Solution {  
 public:  
   void getMaxMinLength(unordered_set<string> &dict, int &maxLength, int &minLength) {  
     maxLength = INT_MIN;  
     minLength = INT_MAX;  
     for (auto elem : dict) {  
       maxLength = max(maxLength, elem.size());  
       minLength = min(minLength, elem.size());  
     }  
   }  
   
   bool wordBreak(string s, unordered_set<string> &dict) {  
     int N = s.size();  
     vector<bool> canBreak(N + 1, false);  
     canBreak[0] = true;  
     int maxLength, minLength;  
     getMaxMinLength(dict, maxLength, minLength);  
     for (int i = 1; i <= N; ++i) {  
       for (int j = i - minLength; j >= 0 && j >= i - maxLength; --j) {  
         if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {  
           canBreak[i] = true;  
           break;  
         }  
       }  
     }  
     return canBreak[N];  
   }  
 };