Leetcode[139] Word Break
11 Nov 2015###Task1 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”. ###Python ####O(n) extra space
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
if not s or not wordDict:
return False
N = len(s)
dp = [False for i in range(N + 1)]
dp[0] = True
for i in range(1, N + 1):
for j in range(i):
if dp[j] and s[j : i] in wordDict:
dp[i] = True
break
return dp[N]
###Java
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
if (s == null || wordDict == null || s == "" || wordDict.size() == 0) {
return false;
}
//break[i] stands for that the previous i char can be separated
boolean[] breaker = new boolean[s.length() + 1];
breaker[0] = true;
int pos = 0;
for (int i = 1; i <= s.length(); i++) {
breaker[i] = false;
for (int j = 0; j < i; j++) {
if (breaker[j] && wordDict.contains(s.substring(j, i))) {
breaker[i] = true;
break;
}
}
}
return breaker[s.length()];
}
}
###Points
- Similar to Word Ladder
- Why dp array larger than the length by 1? cause dp[0] = true, we need a start point.
假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。
###Task2 Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”].
A solution is [“cats and dog”, “cat sand dog”].
###Python
class Solution(object):
def isBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
if not s or not wordDict:
return False
N = len(s)
dp = [False for i in range(N + 1)]
dp[0] = True
for i in range(1, N + 1):
for j in range(i):
if dp[j] and s[j : i] in wordDict:
dp[i] = True
break
return dp[N]
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
if not s or not wordDict:
return []
ret = []
res = self.isBreak(s, wordDict)
if res:
self.findAll(s, wordDict, ret, [])
return ret
def findAll(self, s, wordDict, ret, temp):
if len(s) == 0:
ret.append(' '.join(temp))
return
for i in range(1, len(s) + 1):
if s[:i] in wordDict:
temp.append(s[:i])
self.findAll(s[i:], wordDict, ret, temp)
temp.pop()
###Java
import java.util.*;
public class Solution {
public void helper(String s, Set<String> wordDict, String str, List<String> res, int pos) {
if (pos == s.length()) {
res.add(str);
return;
}
StringBuilder sb = new StringBuilder();
for (int j = pos; j < s.length(); j++) {
sb.append(s.charAt(j));
if (wordDict.contains(sb.toString())) {
String newItem = str.length() > 0 ? (str + " " + sb.toString()) : (sb.toString());
helper(s, wordDict, newItem, res, j + 1);
}
}
return ;
}
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> res = new ArrayList<String>();
if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
return res;
}
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
dp[i] = false;
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
}
}
}
if (dp[s.length()]) {
helper(s, wordDict, "", res, 0);
}
return res;
}
public static void main(String[] args) {
Solution sol = new Solution();
Set<String> wordDict = new HashSet<String>();
wordDict.add("cat");
wordDict.add("cats");
wordDict.add("and");
wordDict.add("sand");
wordDict.add("dog");
List<String> res = sol.wordBreak("catsanddog", wordDict);
for (String s: res) {
System.out.println(s);
}
}
}
从这道题来说，因为是一个NP问题，结果数量有可能就是指数量级的，所以复杂度来说都是指数的，用DP只不过是循环时间复杂度减少了，但是到了赋值给结果的时候还是指数量级的～ 像这种题目就是时间和空间复杂度都取决于结果数量的量级哈～