首页 > 代码库 > ★word_break--leetcode--动态规划

★word_break--leetcode--动态规划

人人为我 递推型 动态规划:
class Solution {
public:
	bool wordBreak(string s, unordered_set<string> &dict){
		int len = s.length();
		vector<bool> match(len + 1, false);
		match[0] = true;
		for (int i = 1; i <= len; i++){
			for (int k = 0; k < i; k++){
				match[i] = match[k] && (dict.find(s.substr(k, i - k)) != dict.end());
				if (match[i]) break;
			}
		}
		return match[len];
	}
};
我为人人 递推型 动态规划:
<p>class Solution {
</p><p>public:
  bool wordBreak(string s, unordered_set<string> &dict) {
    int len = s.length();
    vector<bool> match(len + 1, false);
    match[0] = true;
    for (int i = 1; i <= len; ++i) {
      for (int j = i - 1; j >= 0; --j) {
        if (match[j]) {
          if (dict.find(s.substr(j, i - j)) != dict.end()) {
            match[i] = true;  // 前i个字母可以match
            break;
          }
        }
      }
    }
    return match[len];
  }
};</p>
最长上升字序列:


★word_break--leetcode--动态规划