leetcode--Word Break

时间：2014-02-28 06:04:19 阅读：506 评论：0 收藏：0 [点我收藏+]

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

Have you been asked this question in an interview?

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

leetcode--Word Break,布布扣,bubuko.com

leetcode--Word Break

原文：http://www.cnblogs.com/averillzheng/p/3571147.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)