[leetcode] Word Break

1 problem

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

2 散列容器(hash container)

通常比二叉树的存储方式可以提供更高的访问效率.
#include <boost/unordered_set.hpp>
#include <boost/unordered_map.hpp>
using namespace boost;
散列集合简介:
unordered库提供两个散列集合类unordered_set和unordered_multiset,STLport也提供hash_set和hash_multiset，
它们的接口，用法与stl里的标准关联容器set/multiset相同，只是内部使用散列表代替了二叉树实现，因此查找复杂度由数降为常数。

3 Solution1

很自然想到采用递归来实现，发现超时。

bool wordBreak(string s, unordered_set<string> &dict) {
    if(dict.find(s) != dict.end()){
        return true;                                                                                                                         
    }
    
    bool finished = false;
    for(int i = 1; i< s.length(); i++){
        string first = s.substr(0, i);
        if(dict.find(first)!=dict.end()){
            if(i == s.length()){
                finished = true;
            }else{
                string second = s.substr(i);
                finished = wordBreak(second, dict);
                if(finished){
                    break;
                }
            }
        }
    }
    return finished;
}

给出的例子

4 Solution2

昨天看动态规划，使用条件：

（1）重叠子问题

将一个问题分为若干个子问题的时候，子问题并不是每次都是最新的。因此可以采用空间换时间的方法，将子问题的解记录下来。

（2）最优子结构

原问题的最优解，包含子问题的最优解。

[leetcode] Word Break

原文：http://www.cnblogs.com/erli11/p/3994614.html