首页 > 代码库 > World Break求解两法
World 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".
【方法一】采用递归的方法。该方法最简单最直观。一个循环，判断字符串开头到第i个字符是否匹配，如果匹配则对第i到length个字符组成的子串。这个方法虽然简单，但是运行时间太长，无疑超时。
<span style="font-size:18px;">public static boolean wordBreak(String s, Set<String> dict) {
if(s==null)return false;
if(dict.contains(s)||s.equals(""))return true;
int size=s.length();
for(int i=1;i<size;i++)
{
if(dict.contains(s.substring(0,i)))
{
if(wordBreak(s.substring(i),dict))return true;
}
}
return false;
}</span>【方法二】对方法一进行改进，用一个Boolean数组来保存前i个字符的匹配结果，显然数组的长度为length+1。外层循环依次取原字符串各个长度的子字符串；内层循环判断当前子串是否能找到切分方式，只要找到一种切分方式就说明长度为i的单词可以成功切分，因此可以跳出内层循环。 <span style="font-size:18px;">public static boolean wordBreak2(String s, Set<String> dict)
{
boolean []match=new boolean[s.length()+1];
match[0]=true;
for(int i=1;i<=s.length();i++)
for(int j=i-1;j>=0;j--)
{
if(match[j]&&dict.contains(s.substring(j, i)))
{
match[i]=true;
break;
}
}
return match[s.length()];
}</span>这两个算法的效率都不高，这个问题一定还有高效的算法，欢迎补充World Break求解两法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。