问题描述
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. dfs，超时；
2. dp。
使用一个大小为输入字符串长度加1的辅助数组，dp[i]表示S[0, i]字符串是否可以被分割。
双重for循环，时间复杂度为O(n^2).
程序
1. DFS
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
if (s == null || s.length() == 0) {
return true;
}
if (wordDict == null || wordDict.size() == 0) {
return false;
}
return helper(s, wordDict);
}
private boolean helper(String s, Set<String> wordDict) {
if (s.length() == 0) {
return true;
}
boolean flag = false;
for (int i = 0; i < s.length(); i++) {
String word = s.substring(0, i + 1);
if (wordDict.contains(word)) {
flag = helper(s.substring(i + 1), wordDict);
}
}
return flag;
}
}
2. DP
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
if (s == null || s.length() == 0) {
return true;
}
if (wordDict == null || wordDict.size() == 0) {
return false;
}
return helper(s, wordDict);
}
private boolean helper(String s, Set<String> wordDict) {
if (s.length() == 0) {
return true;
}
boolean flag = false;
for (int i = 0; i < s.length(); i++) {
String word = s.substring(0, i + 1);
if (wordDict.contains(word)) {
flag = helper(s.substring(i + 1), wordDict);
}
}
return flag;
}
}
原文：http://www.cnblogs.com/harrygogo/p/4677950.html