# Word Break - tags: [[DP_Sequence](# "單序列動態規劃，通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。")] ### Source - leetcode: [Word Break | LeetCode OJ](https://leetcode.com/problems/word-break/) - lintcode: [(107) Word Break](http://www.lintcode.com/en/problem/word-break/) ~~~ 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". ~~~ ### 題解 單序列([DP_Sequence](# "單序列動態規劃，通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。")) DP 題，由單序列動態規劃的四要素可大致寫出： 1. State: `f[i]` 表示前`i`個字符能否根據詞典中的詞被成功分詞。 1. Function: `f[i] = or{f[j], j < i, letter in [j+1, i] can be found in dict}`, 含義為小于`i`的索引`j`中只要有一個`f[j]`為真且`j+1`到`i`中組成的字符能在詞典中找到時，`f[i]`即為真，否則為假。具體實現可分為自頂向下或者自底向上。 1. Initialization: `f[0] = true`, 數組長度為字符串長度 + 1，便于處理。 1. Answer: `f[s.length]` 考慮到單詞長度通常不會太長，故在`s`較長時使用自底向上效率更高。 ### Python ~~~ class Solution: # @param s, a string # @param wordDict, a set<string> # @return a boolean def wordBreak(self, s, wordDict): if not s: return True if not wordDict: return False max_word_len = max([len(w) for w in wordDict]) can_break = [True] for i in xrange(len(s)): can_break.append(False) for j in xrange(i, -1, -1): # optimize for too long interval if i - j + 1 > max_word_len: break if can_break[j] and s[j:i + 1] in wordDict: can_break[i + 1] = True break return can_break[-1] ~~~ ### C++ ~~~ class Solution { public: bool wordBreak(string s, unordered_set<string>& wordDict) { if (s.empty()) return true; if (wordDict.empty()) return false; // get the max word length of wordDict int max_word_len = 0; for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); ++it) { max_word_len = max(max_word_len, (*it).size()); } vector<bool> can_break(s.size() + 1, false); can_break[0] = true; for (int i = 1; i <= s.size(); ++i) { for (int j = i - 1; j >= 0; --j) { // optimize for too long interval if (i - j > max_word_len) break; if (can_break[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()) { can_break[i] = true; break; } } } return can_break[s.size()]; } }; ~~~ ### Java ~~~ public class Solution { public boolean wordBreak(String s, Set<String> wordDict) { if (s == null || s.length() == 0) return true; if (wordDict == null || wordDict.isEmpty()) return false; // get the max word length of wordDict int max_word_len = 0; for (String word : wordDict) { max_word_len = Math.max(max_word_len, word.length()); } boolean[] can_break = new boolean[s.length() + 1]; can_break[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = i - 1; j >= 0; j--) { // optimize for too long interval if (i - j > max_word_len) break; String word = s.substring(j, i); if (can_break[j] && wordDict.contains(word)) { can_break[i] = true; break; } } } return can_break[s.length()]; } } ~~~ ### 源碼分析 Python 之類的動態語言無需初始化指定大小的數組，使用時下標`i`比 C++和 Java 版的程序少1。使用自底向上的方法求解狀態轉移，首先遍歷一次詞典求得單詞最大長度以便后續優化。 ### 復雜度分析 1. 求解詞典中最大單詞長度，時間復雜度為詞典長度乘上最大單詞長度 O(LD?Lw)O(L_D \cdot L_w)O(LD?Lw) 1. 詞典中找單詞的時間復雜度為 O(1)O(1)O(1)(哈希表結構) 1. 兩重 for 循環，內循環在超出最大單詞長度時退出，故最壞情況下兩重 for 循環的時間復雜度為 O(nLw)O(n L_w)O(nLw). 1. 故總的時間復雜度近似為 O(nLw)O(n L_w)O(nLw). 1. 使用了與字符串長度幾乎等長的布爾數組和臨時單詞`word`，空間復雜度近似為 O(n)O(n)O(n).