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开始到最后的子字符串是不是可以划分。将字符串从后往前遍历,填写数组statuspublic 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]; } }
原文:http://blog.csdn.net/u010378705/article/details/28320757