首页 > 试题广场 > word-break
[编程题]word-break
给定一个字符串s和一组单词dict,判断s是否可以用空格分割成一个单词序列,使得单词序列中所有的单词都是dict中的单词(序列可以包含一个或多个单词)。
例如:
给定s=“leetcode”;
dict=["leet", "code"].
返回true,因为"leetcode"可以被分割成"leet code".

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

/**
	   * 方法二:
	   * 状态转移方程:
	   * f(i) 表示s[0,i]是否可以分词
	   * f(i) = f(j) && f(j+1,i); 0 <= j < i;
	   * 
	   */
	  public boolean wordBreak2(String s, Set<String> dict){
	    int len = s.length();
	    boolean[] arrays = new boolean[len+1];
	    arrays[0] = true;
	    for (int i = 1; i <= len; ++i){
	      for (int j = 0; j < i; ++j){
	        if (arrays[j] && dict.contains(s.substring(j, i))){
	          arrays[i] = true;
	          break;
	        }
	      }
	    }
	    return arrays[len];
	  }

发表于 2016-05-11 17:16:34 回复(7)
用动态规划,dp[i]表示字符串s[0~i]是否可分的bool值。
        int len = s.length();
        vector<bool> dp(len+1,false);
        dp[0]=true;
        for(int pos=0;pos<len;++pos)
            for(int i=pos;dp[pos] && i<len;++i)
            	if (dict.find(s.substr(pos,i-pos+1))!=dict.end())
            		dp[i+1]=true;
        return dp[len];

发表于 2016-08-03 17:54:42 回复(6)
//有几个需要注意的边界点
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int i,j;
        boolean array[]=new boolean[s.length()+1];//此处的Array大小
        array[0]=true;//此处的初始化
        for(i=1;i<array.length;i++) {
            for(j=0;j<i;j++) {
                if(array[j]&&dict.contains(s.substring(j, i))) {
                    array[i]=true;//此处的SubString
                    break;
                }
            }
        }
        return array[array.length-1];//此处的返回值
    
    }
}

发表于 2018-06-10 11:34:09 回复(1)
import java.util.*;
//题意:把wordDict中的元素进行组合,可以重复使用,是否可以拼成s
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] res = new boolean[s.length() + 1];
		res[0] = true;
        //i循环的目的是,确定能不能拼成以i为下标结尾的字符串
        for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < i; j++) {
				if(res[j]&&dict.contains(s.substring(j, i))){
					res[i]=true;
					//只要找到一个 能拼成以i为下标结尾的字符串,就可以跳出循环
					break;
				}
			}
		}

		return res[s.length()];
    }
}

发表于 2017-07-15 12:26:44 回复(0)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        vector<bool> v(len+1,false);
        v[0] = true;
        for(int i = 1;i <= len; i++)
            {
            for(int j = i-1; j >= 0; j--)
                {
                if(v[j] && dict.find(s.substr(j,i-j))!= dict.end())
                    {
                    v[i] = true;
                    break;
                }
            }
        }
        return v[len];
    }
};

发表于 2017-05-10 20:28:44 回复(0)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int l = s.length();
        vector<bool> dp(l+1, false);
        dp[0] = true;
        for(int i=0;i<l;i++)
            for(int j=i;j<l && dp[i];j++)
                if(dict.find(s.substr(i, j-i+1)) != dict.end())
                    dp[j+1] = true;
        return dp[l];
    }
};

发表于 2017-09-23 13:28:09 回复(0)
/**
* 出发点:给定字符串s的每个字符i
* 最优解:对于每个i之前的字符序列,分为j(0<=j<=i)前面的序列和j后面的序列,求解i转化为求解j和i-j
* 状态d(i):i之前的字符序列分段后的字符串能不能在字典中找到
* 递推公式:d(i) = d(i)||(d(j)&sub(i-j)), 其中j=0~i
*/
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] d = new boolean[len];
        for (int k=0; k<len; k++)
            d[k] = false;
        String sub = null;
        boolean subFlag = false;
         
        for (int i=0; i<len; i++) {
            for (int j=0; j<=i; j++) {
                sub = s.substring(j, i+1);
                subFlag = dict.contains(sub);
                if (j==0) d[i] = subFlag;
                else d[i] = d[i]||(d[j-1]&&subFlag);
            }
        }
         
        return d[len-1];
    }
}

发表于 2017-08-16 10:25:13 回复(0)
//动态规划问题
public class WordBreak
{
    public boolean wordBreak(String s, Set<String> dict)
    {
        if (s == null || s.length() == 0)
        {
            return true;
        }
        int len = s.length();
        // 正确截取单词的标记(开始索引)
        boolean dp[] = new boolean[len + 1];
        // 初始
        dp[0] = true;
        for (int i = 0; i < len; i++)
        {
            // substring方法 切割字符串 不包含i+1的哪一个位
            StringBuilder str = new StringBuilder(s.substring(0, i + 1));
            for (int j = 0; j <= i; j++)
            {
                if (dp[j] && dict.contains(str.toString()))
                {
                    dp[i + 1] = true;
                    break;
                }
                // 删除str的第一个字符(因为str是从s的头字符开始截取的)
                str.deleteCharAt(0);
            }
        }
        // 如果都能正确匹配 则dp[len]=true
        return dp[len];
    }
}

发表于 2017-05-26 21:12:12 回复(0)
class Solution{
public:
    bool wordBreak(string s, unordered_set<string> &dict){
		vector<bool>dp(s.size(), false);
		for (int j = 0; j < s.size(); j++)if (dict.find(s.substr(j, s.size() - j)) != dict.end())dp[j] = true;
		for (int i = s.size() - 2; i >= 0; i--)
			for (int j = 0; j <= i; j++)
				if (dict.find(s.substr(j, i - j + 1)) != dict.end())dp[j] = dp[j] || dp[i + 1];
		return dp[0];
	}
};

发表于 2019-08-16 20:29:37 回复(0)

动态规划问题

记:

        dp[j] :                   子串 s[i..j)是否能被拆分为词典单词
    初始化:
        dp[0] = true         由于是右开空间s[0]预设为true方便遍历
    递推公式: 
        dp[j] = dp[i] && dp[i,j)即substr(i, j - i)           注意dp[j]是左闭右开空间

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        //字符串结束位置,左闭右开s[i,j)
        for(auto j = 1; j <= s.size(); ++j)
            for(auto i = j - 1; i >= 0; --i){//字符串起始位置
                if(dp[i] && dict.find(s.substr(i, j - i)) != dict.end()){
                    dp[j] = true;
                    break;
                }
            }
        return dp[s.size()];
        
    }
};

编辑于 2019-05-01 21:33:16 回复(0)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(dict.find(s)!=dict.end()) return true;
        int size=s.size();
        for(int i=size-1;i>0;--i)
        {
            string word=s.substr(i);
            if(dict.find(word)==dict.end()) 
                continue;
            if(wordBreak(s.substr(0,i),dict)) return true;
        }
        return false;
    }
};

发表于 2019-04-28 09:02:59 回复(0)

简单的 dp 解法:

import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
发表于 2019-04-04 23:49:01 回复(0)
 class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        /*
            dp[i]表示string从0到i能够被分割
            dp[i] = dp[j]&&substring(j,i) ,其中0<=j<i 
        */
        int length = s.length();
        int *dp = new int[length+1]();
        dp[0]=1;
        for(int i=1;i<=length;i++){
            for(int j=0;j<i;j++){
                if(dp[j]==1 && dict.find(s.substr(j,i-j))!=dict.end()){ 
                    dp[i]=1;
                    break;
                }
            }
        }
        return dp[length];
    }
};

发表于 2019-03-24 20:00:55 回复(0)
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<string> dict) {
        boolean dp[] = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
</string>

发表于 2019-01-21 21:47:18 回复(0)
比普通DP有三个优化:
  1. 字典采用hash表存储;
  2. 并根据单词长度把hash表分开,这样查询速度更快;
  3. 记录单词步长,只去匹配存在的步长,比如单词全是4个字母,每次step为4就可以了。
class Solution(object):
    def wordBreak(self, s, wordDict):
        if len(wordDict) == 0:
            return False
        l = max(map(lambda x: len(x), wordDict))
        m = [{} for i in range(l + 1)]
        steps = []
        for w in wordDict:
            if len(w) not in steps:
                steps.append(len(w))
            m[len(w)][w] = 1

        dp = [0] * (len(s) + 1)
        dp[0] = 1
        for i in range(len(s)):
            if dp[i] == 0:
                continue
            for step in steps:
                if s[i:i + step] in m[step]:
                    if i + step <= len(s):
                        dp[i + step] = 1
        return dp[len(s)] == 1

编辑于 2017-10-08 21:45:02 回复(0)
import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s == null || s.length() <= 0)
        	return true;
        if(dict == null || dict.size() <= 0)
        	return false;
        
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++){
        	for(int j = 0; j < s.length(); j++){
        		if(dp[j] && dict.contains(s.substring(j, i))){
        			dp[i] = true;
        			break;
        		}     			
        	}
        }
        return dp[s.length()];
    }
}

发表于 2017-05-15 19:01:34 回复(2)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
       int n,i,j,len;
       n = s.size();
       vector<int> can(n+1,0);
       string sub;
       unordered_set<string>::iterator it;
       len = 0;
       for(it=dict.begin();it!=dict.end();it++){
         if(len < it->size()){len = it->size();}//找到最大子串长。
       }
       can[n] = 1;
       for(i=n-1;i>=0;i--){
         sub = "";
         for(j=i;j<n;j++){
           sub += s[j];
           if(j-i<len && dict.count(sub) && can[j+1]){can[i] = 1;}
         }
       }
       return can[0];
    }
};
大家都用的动态规划,不过我在规划之前会先计算最大子串的长度,这样可以进一步提高效率。
发表于 2016-12-14 16:50:18 回复(0)
import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
		// dp[i]表示0到i位可分
		boolean[] dp = new boolean[len + 1];
		dp[0] = true;
		for (int i = 1; i <= len; i++) {
			for (int j = 0; j < i; j++) {
				if (dp[j] && dict.contains(s.substring(j, i))) {
					dp[i] = true;
				}
			}
		}
		return dp[len];
    }
}

发表于 2016-10-12 11:18:04 回复(0)
if(s.empty()&&dict.find("")==dict.end())
            return false;
        vector<bool> flag(s.size()+1,false);
        flag[0] = 1;
        for(int i=1;i<=s.size();i++){
            for(int j=i-1;j>=0;j--){
                if(flag[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
                    flag[i] = 1;
                    continue;
                }
            }
        }
        return flag[s.size()];
发表于 2016-08-16 09:16:45 回复(0)
动态规划,画一个表格,就能看出来
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int length=s.length();
		if(length<1)
			return true;
		boolean[] dp=new boolean[length+1];//默认值为false
		dp[0]=true;
		for(int i=0;i<length;i++){
			if(dp[i]){
				for(int j=i;j<length;j++){
					if(dict.contains(s.substring(i,j+1))){
						dp[j+1]=true;
					}
				}
			}
		}
		return dp[length];
    }
}

发表于 2016-04-19 11:23:06 回复(1)