Table of Contents
Leetcode 139: Word Break
Problem
Given a string s
and a dictionary of strings wordDict
, return true
if s
can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false
Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
andwordDict[i]
consist of only lowercase English letters.- All the strings of
wordDict
are unique
C++ Code
class Solution { public: bool rec(string& s, set<string>& all_words, int begin_index, vector<int>& memo){ if(begin_index == s.length()) //we reached end of the string, that means, whatever words we found so far, matched with any of the dictionary words return true; if(memo[begin_index] != -1) //that means, we came to this index before and know the result is either 0 or 1 return memo[begin_index]; for(int cur_index = begin_index + 1; cur_index <= s.length(); cur_index++){ //Now, we will make words of 1, 2, 3....n characters beginning from begin index string cur_word = s.substr(begin_index, cur_index - begin_index); //Then we will check if this word is a dictionary word or not if(all_words.find(cur_word) != all_words.end()){ /* When this length of word belongs to the dictionary word, we don't need to check anything for it. So we will call the recursion passing ending index as the beginning index and see if we can find a dictionary word from the next constructed words. This way, if we continue to keep finding, the function will reach its terminate condition after some time. But, if we do not reach the terminate condition, we will come back to this loop eventually and create a new cur_word with the next length and call the recursion again.*/ if(rec(s, all_words, cur_index, memo) == true) return memo[begin_index] = true; } } return memo[begin_index] = false; } bool wordBreak(string s, vector<string>& wordDict) { //set of all words is generated here set<string> all_words(wordDict.begin(), wordDict.end()); /* we will use a memoization table to keep track of an index is used or not. By used, we mean that, starting from this index, we found a word and that word is used. If it is not used yet, -1 is assigned for that If it is used, but we didn't find any result, we put 0 If it is used, but we found any result, we put 1 */ vector<int> memo(s.length(), -1); return rec(s, all_words, 0, memo); } };
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
Hi foolishhungry.com administrator, Great content!
Hello foolishhungry.com administrator, Your posts are always on topic and relevant.
Hello foolishhungry.com administrator, Good work!
Hi foolishhungry.com admin, Your posts are always insightful and valuable.
Hi foolishhungry.com webmaster, You always provide great examples and real-world applications.
To the foolishhungry.com administrator, Your posts are always well-supported and evidence-based.
You’ve provided useful knowledge that will undoubtedly help me in my endeavors.
Hi foolishhungry.com webmaster, Your posts are always well received by the community.
Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://accounts.binance.com/en/register-person?ref=V2H9AFPY
Hello foolishhungry.com owner, Your posts are always well organized and easy to understand.
Hi foolishhungry.com owner, Your posts are always well-supported by facts and figures.
To the foolishhungry.com webmaster, Good work!
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://www.binance.info/sl/join?ref=53551167
Dear foolishhungry.com webmaster, You always provide in-depth analysis and understanding.
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.info/join?ref=P9L9FQKY
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.com/ka-GE/join?ref=V2H9AFPY
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.info/fr/join?ref=53551167
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
Your article helped me a lot, is there any more related content? Thanks!
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
Hi foolishhungry.com admin, Your posts are always a great source of knowledge.