爱程序网

[LeetCode] 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".

     这道题还是挺有难度的。重点是dynamic programming的应用。用boolean[]来判断true/false与否。记得除了contians()的条件外还要判断两个被分开的单词是否连在一起这样的问题。

     代码如下。~

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s==null&&s.length()==0){
            return false;
        }
        int len=s.length();
        
        boolean[] test=new boolean[len];
        for(int i=0;i<len;i++){
            for(int j=0;j<=i;j++){
               String sub=s.substring(j,i+1);
               if(wordDict.contains(sub)&&(j==0||test[j-1])){
                   test[i]=true;
                   break;
               }
            }
        }
        return test[len-1];
    }
}

 

关于爱程序网 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 人才招聘 - 帮助