首页 > 其他 > 详细

Word Break

时间:2014-06-07 13:53:44      阅读:313      评论: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".


方法
定义一个数组status,长度为字符串的长度,用来表示从k开始到最后的子字符串是不是可以划分。
将字符串从后往前遍历,填写数组status
	  public boolean wordBreak(String s, Set<String> dict) {
		  
		  if (s == null) {
			  return false;
		  } else if (s.length() == 0){
			  return false;
		  } else if (s.length() == 1) {
			  if (dict.contains(s)) {
				  return true;
			  } else {
				  return false;
			  }
		  } else {
			  int len = s.length();
			  
			  int maxLen = 0;
			  int minLen = 100;
			  for (String str: dict) {
			  	if (str.length() > maxLen) {
			  		maxLen = str.length();
			  	} 
			  	if (str.length() < minLen) {
			  		minLen = str.length();
			  	}
			  }
			  
			  boolean[] status = new boolean[len + 1];
			  status[len] = true;
			  
			  for (int i = len - 1; i >= 0; i--) {
				  for (int j = i + minLen ; j <= Math.min(len, maxLen + i); j++) {
					  String subStr = s.substring(i, j);
					  if (dict.contains(subStr) && status[j]) {
						  status[i] = true;
						  break;
					  }
					  status[i] = false;
				  }
			  }
			  return status[0];
		  }	  
	}


Word Break,布布扣,bubuko.com

Word Break

原文:http://blog.csdn.net/u010378705/article/details/28320757

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!