Lintcode: word break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Have you met this question in a real interview? 

Yes

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Tags Expand 

String Dynamic Programming

Reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-word-break-i-ii.html

s1: dp[i] -- can the beginning i char can be broken
s2: dp[i + 1] (0 <= i < s.size) ==> whether exists s[k--i] is in dictionary && dp[k] is true (whether s[0--k-1] is true)
s3: dp[0] = true

Time: O(n*n)   -- n is len of string
Space: O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

class Solution { public: /** * @param s: A string s * @param dict: A dictionary of words dict */ bool wordBreak(string s, unordered_set<string> &dict) { // write your code here vector<bool> dp(s.size() + 1, false); dp[0] = true; //annotation part is used to pass lintcode, not necessary for leetcode // Filter out impossible string which alphabet set is not covered by dict. /* unordered_set<char> chrs; for (const auto& word : dict) { for (const auto& c : word) { chrs.insert(c); } } for (const auto& c : s) { if (chrs.find(c) == chrs.end()) return false; } */ for(int i = 0; i < s.size(); i++){ //string str = ""; for(int k = i; k >= 0; k--){ //str = s[k] + str; if(dp[k] && dict.count(s.substr(k, i - k + 1)) ){ dp[i + 1] = true; break; } } } return dp[s.size()]; } };