首页 > 试题广场 >

拆分词句

[编程题]拆分词句

热度指数：61072 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。

例如:
给定s=“nowcode”；
dict=["now", "code"].
返回true，因为"nowcode"可以被分割成"now code".

算法知识视频讲解

小刀初试

用动态规划，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 回复(7)

Java

中本聪007

//有几个需要注意的边界点
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)

JacobGo！

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)

gwhmma

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)

C/C++

nbgao

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)

Ctrl+F5

/**
* 出发点：给定字符串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)

wangChaoNK

//动态规划问题
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)

C++

喝醉了Ta的梦,晚安

直接动态规划就可以

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        //bilibilihelloworld  ---  {"bilibili","world","hello"}
        int n = s.length();
        // F(i)  前i个字符可否被分割
        vector<bool> F(n+1,false);
        F[0] = true;
        for(int i=1;i<=n;++i)
        {
            for(int j=i-1;j>=0;--j)
            {
                if(F[j]&&dict.find(s.substr(j,i-j))!=dict.end())
                {
                    F[i]=true;
                    break;
                }
            }
        }
        return F[n];
    }
};

发表于 2021-12-28 23:42:39 回复(0)

Taro

class Solution {
public:
    bool wordBreak(string s, unordered_set &dict) {
        int l = s.length();
        bool* dp = new bool[l+1];
        dp[0]=true; //空字符，设定为true
        for(int i=1;i<=l;i++)
        {   
            dp[i]=false; //初始化为false
            for(int j=i;j>0;j--)
            {
                string cur_s = s.substr(j-1,i-j+1); //注意下标
                if(dict.count(cur_s)>0 && dp[j-1])
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[l];

    }
};

发表于 2020-05-20 23:56:40 回复(0)

ExtraLocker

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        int dp[len+1];
        dp[0] = 1;
        for (int i = 1; i <= len; i++) dp[i] = 0;
        for (int i = 1; i <= len; i++) {
            for (int j = i; j > 0; j--) {
                dp[i] = dp[i] || dp[j-1] && dict.count(s.substr(j - 1, i - j + 1)) != 0;
            }
        }
        return dp[len];
    }
};

发表于 2020-04-16 18:37:50 回复(0)

C/C++

求份offer压压惊

1.既然动态规划需求存储历史信息，那我们首先应该确认我们要存储的历史信息。这里我用boolean loca[i]表示到字符串s的第i个字符时，是否可以用dict中的词来表示。
2.然后，我们假设我们有loca[0…i-1]的结果，那么loca[i]的值应该是：loca[i] = loca[j] && s.substring(j, i + 1) in dict，其中j属于[0…i - 1]。这也就是我们所说的状态方程。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(int i = 1; i <= s.size(); i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && dict.find(s.substr(j, i-j)) != dict.end()){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.size()-1];
    }
};

发表于 2020-04-16 10:08:23 回复(0)

deven_zhu

class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int i,j,start =0,pre_start=0;
bool do_it = false;
int len = s.length();
if (len == 0)
return false;

bool *dp = new bool[len+1];
memset(dp,0,len+1);

dp[0] = true;
for (i = 0; i < len; i++) {
for (j = 1; j < len-i+1;j++) {
if (dp[i] && dict.find(s.substr(i,j)) != dict.end()) {
dp[i+j] = true;
do_it=true;
}
}

}
return do_it && dp[len];
}

};

嵌套的for循环用来穷举每一个可能的字符串，判断一个字符串是否满足条件的前提是：前面相邻的字符串要符合条件，判断过的字符串就用数组记录下结果避免重复计算

发表于 2020-02-23 19:40:16 回复(0)

张佃鹏

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        return dfs(s, dict, new HashMap<String, Boolean>());
    }
     public boolean dfs(String s, Set<String> dict, HashMap<String, Boolean> map) {
        if(map.containsKey(s)){
            return map.get(s).booleanValue();
        }
        boolean result = false;
        for(int i = 0; i < s.length(); i++){
            if(dict.contains(s.substring(0, i + 1)) && (i == s.length() - 1 || dfs(s.substring(i + 1), dict, map))){
                result = true;
                break;
            }
        }
        map.put(s, new Boolean(result));
        return result;
    }
}

发表于 2019-10-05 21:14:11 回复(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)

风中追风20180314092925

动态规划问题

记：

        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)

C/C++

但求八月九月好运！

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)

Java

big_dreamer

简单的 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)

secndf

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有三个优化：

字典采用hash表存储；
并根据单词长度把hash表分开，这样查询速度更快；
记录单词步长，只去匹配存在的步长，比如单词全是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)

提交观点

问题信息

动态规划

难度：

134条回答 287收藏 35067浏览

通过挑战的用户

查看代码

GXR1116

2023-03-08 15:15:55
牛客79086...

2023-01-26 22:05:03
牛客43677...

2023-01-24 14:32:39
xiaoloc...

2023-01-16 10:29:39
虔诚祈求大厂O...

2023-01-14 00:11:52

拆分词句

动态规划问题

记：

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

问题信息

热门推荐

通过挑战的用户

相关试题

拆分词句

动态规划问题

记：

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

问题信息

热门推荐

通过挑战的用户

相关试题

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