现在的位置: 首页 > 综合 > 正文

LeetCode OJ –问题与解答 Word Break

2014年04月05日 ⁄ 综合 ⁄ 共 2403字 ⁄ 字号 评论关闭
题目


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

判断一个字符串,能否被字典里的字符串所切割?


思路1


1 对 待判断字符串S 进行 DFS。查找每个字典的元素,如果匹配,S 跳到下一个坐标,直到S 全部检查完。

2 缺点: 考虑到S 是一个字符串,由很多a 组成,最后是b;字典就是a。这样会花很多时间。第一次对s的第一个a 检查,匹配;再第二个,第三个,直到最后一个不匹配;然后再重新对s的头两个 aa 对字典进行匹配...

3 时间是指数级别的

代码1


public boolean wordBreak(String s, Set<String> dict) {
		        return worddfs(s,dict);
		    }
		    
		    public boolean worddfs(String s,Set<String> dict){
		        if(s.equals("")){
		            return true;
		        }
		     
		        for(int i=0;i<s.length();i++){
		            String temp = s.substring(0,i+1);
		            if(dict.contains(temp)){
		                if(i==s.length()-1){
		                    return true;
		                }
		                if(worddfs(s.substring(i+1),dict)){
		                    return true;
		                }
		            }
		        }
		        return false;
		    }

思路2


1 时间不行,有很多重复检查了。那么考虑从底向上的字典dfs。需要一个二维数组mp。

2 mp[i][j] 代表 S 从i 到j 是否可以匹配。只要存在k mp[i][k] 和 mp[k][j] 都为true的时候,mp[i][j] 也为true。

3 我们需要求的就是mp[0][n-1]

4 时间是O(n3)


代码2


public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
      if(s.length()==0){
          return false;
      }
      int n = s.length();
      boolean[][] ans = new boolean[n][n];
      for(int i=0;i<n;i++){
          for(int j=i;j<n;j++){
              if(dict.contains(s.substring(i,j+1))){
                  ans[i][j]=true;
              }
          }
      }
      for(int i=0;i<n;i++){
          for(int j=i;j<n;j++){
              for(int k=i;k<=j;k++){
                  if(!ans[i][j]){
                      ans[i][j]=ans[i][k]&&ans[k+1][j];
                  }
              }
          }
      }
      return ans[0][n-1];
    }
}

思路3


1 虽然accept,但是时间不够好。继续思考。

2 发现其实我们要求的只是ans[0][n-1]。然后对于每个0行的元素,也就是string 0--i,只有在他之前的0-j是true和ans[j][i]是true的时候才true。

3 所以我们只要再多一个memo[n+1]的数组,来记录每个0-j是否为true,结合上面的ans数组,就可以判断了。

4 时间缩小到O(n2), dp的技巧让 空间换时间。

代码3


public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
      if(s.length()==0){
          return false;
      }
      int n = s.length();
      boolean[][] ans = new boolean[n][n];
      for(int i=0;i<n;i++){
          for(int j=i;j<n;j++){
              if(dict.contains(s.substring(i,j+1))){
                  ans[i][j]=true;
              }
          }
      }
      boolean[] memo = new boolean[n+1];
      memo[0]=true;
      for(int i=0;i<n;i++){
          for(int j=0;j<=i;j++){
              if(memo[j]&&ans[j][i]){
                      memo[i+1]=true;
                }
                  
              
          }
      }
      return memo[n];
    }
}

思路4


1 上面的二维数组空间有点多余了,可以不用那个空间。

2 从最小的字符串(0,0) 开始检查,如果是true,代表是这个字符串在字典中;然后再根据字典,看看可以延伸到哪几个位子,标注为true,直到字典检查结束。之后,查看下个标注为true的位子,再根据字典,把可以延伸的继续找到。看看最后能不能到达n-1。

3 这是从dfs 一步步演化到dp,只适用于这道题目的最简便算法了。

代码4


public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
      boolean[] canBreak = new boolean[s.length()+1];
      canBreak[0] = true;
      for(int i=0; i<s.length(); i++){  
            if(canBreak[i] == false){  
                continue;  
            }  
            for(String dictS : dict){  
                int len = dictS.length();  
                int end = i + len;  
                if(end > s.length()){  
                    continue;  
                }  
                if(s.substring(i, end).equals(dictS)){  
                    canBreak[end] = true;  
                }  
            }  
        }  
        return canBreak[s.length()];  
    }
}


抱歉!评论已关闭.