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

解题思路：

解法1，回溯法。但会超时。其时间复杂度为len!

class Solution {
public:
    bool wordBreak(string s, unordered_set& wordDict) {
        return helper(s, wordDict);
    }
    
    bool helper(string s, unordered_set& wordDict){
        if(s==""){
            return true;
        }
        int len = s.length();
        for(int i=1; i<=len; i++){
            if(wordDict.find(s.substr(0, i))!=wordDict.end() && helper(s.substr(i), wordDict)){
                return true;
            }
        }
        return false;
    }
};

解法2，动态规划。对于d[i]表示字符串S[0,..., i]费否能够被字典拼接而成。于是有

d[i] = true, 如果s[0,...i]在字典里面

d[i] = true, 如果存在k，0

d[i] = false, 不存在这样的k

代码如下：

class Solution {
public:
    bool wordBreak(string s, unordered_set& wordDict) {
        int len = s.length();
        if(len == 0){
            return true;
        }
        bool d[len];
        memset(d, 0, len * sizeof(bool));
        if(wordDict.find(s.substr(0, 1)) == wordDict.end()){
            d[0] = false;
        }else{
            d[0] = true;
        }
        for(int i=1; i
时间复杂度为O(len^2)


另外，一个非常好的解法就是添加一个字符在s前面，使得代码更加简洁。
class Solution {
public:
    bool wordBreak(string s, unordered_set& wordDict) {
        s = "#" + s;
        int len = s.length();
        bool d[len];
        memset(d, 0, len * sizeof(bool));
        d[0] = true;
        for(int i=1; i

 
转载请注明： » [LeetCode] Word Break

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->