Word Break ii | LeetCode 140 | C++, Python

LeetCode Solutions: • LeetCode Solutions | L...
June LeetCoding Challenge: • Playlist
May LeetCoding Challenge: • Playlist
Github Link: github.com/KnowledgeCenterYou...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
July LeetCoding Challenge | Problem 30 | Word Break ii | 30 July,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Word Break ii,
Word Break ii c++,
Word Break ii Java,
Word Break ii python,
Word Break ii solution,
140. Word Break ii,
#CodingInterview #LeetCode #JulyLeetCodingChallenge #Google #Amazon #WordBreak

[@cbjueueiwyru7472]

Thanks. Out of all the solutions on youtube, yours was the most understandable!

[@KnowledgeCenter]

Great to hear!

[@sase1017]

Can you solve it from bottom-up approach? and talk about the difference btw top-down and bottom-up?

[@vadirajjahagirdar2615]

Neatly explained. .Thanks

[@richakhurana5372]

Thank you a lot, Sir! Could you please also explain how to solve it without memoization, if possible?

[@rodrickedwards2759]

Thanks!

[@NoName-ip4tt]

one of the best explanation of this problem. Thnx!

[@KnowledgeCenter]

Glad you liked it!

[@dhruvamin197]

Is the TC for this: O(len(s) * len(wordDict)) ?

[@rohitkhandelwal2894]

Best solution in youtube ,very simple

[@KnowledgeCenter]

Glad to hear.

[@karanbobade5266]

what is the time complexity of the solution

[@susrandomguy]

Thank you for the explanation.

[@KnowledgeCenter]

Glad it was helpful!

[@christopherbrooke5980]

genius code!

[@infoto23]

Thank you for the solution for this! One question though: what is the time and space complexity of the solution above? (with and without caching/memoization)
Thanks again

[@haaarshiiiit]

I have the same question !?

[@learner_1228]

did you find?

[@sheldon9415]

Thank you, great explanation!What would the time and space complexity be for this problem?

[@saichennu5288]

Sir please solve reorder data in log files leetcode problem

[@shishpalvishnoi7974]

Can Trie be used here?

[@wulymammoth]

fair question -- it will exceed the time-limit, because the trie saves you space, but at what cost? that cost is time. you still have to perform linear scan on substrings. the hashmap/dictionary reduces substring postfix look-ups to O(1)

[@floatingpoint7629]

Please do word break i too.

[@ashishupadhyay6881]

Your solution is not submitting on interviewbit for large inputs.
Your submission failed for the following input:
A : "aabbbabaaabbbabaabaab"
B : [ "bababbbb", "bbbabaa", "abbb", "a", "aabbaab", "b", "babaabbbb", "aa", "bb" ]

[@avinashprajapati4886]

I also have same case...

[@haaarshiiiit]

What is the time complexity of the recursive solution , without DP / Memoization ??

[@learner_1228]

did you find?

[@ANAS-ex3ru]

n^2 * 2^n

[@SR-we1vl]

Java Solution
class Solution {
Map memo = new HashMap();

public List wordBreak(String s, List wordDict) {
if (memo.containsKey(s)) return memo.get(s);

List res = new ArrayList();

for (String word : wordDict) {
if (s.startsWith(word)) {
if (s.length() == word.length())
res.add(word);
else {
List sub = wordBreak(s.substring(word.length()), wordDict);
for (String w : sub)
res.add(word + " " + w);
}
}
}

memo.put(s, res);
return memo.get(s);
}
}

[@aditgulia]

If looking for Java Solution,
class Solution {
HashMap map = new HashMap();
public List wordBreak(String s, List wordDict) {
List result = new ArrayList();
if (map.containsKey(s))
return map.get(s);
for (String w : wordDict) {
if (w.length() > s.length())
continue;
String firstWord = s.substring(0, w.length());
if (firstWord.equals(w)) {
if (s.length() == w.length()) {
result.add(0, w);
} else {
String leftOne = s.substring(w.length(), s.length());
List tmp = wordBreak(leftOne, wordDict);
for (String val : tmp) {
String sb = w + " " + val;
result.add(0, sb);
}
}
}
}
map.put(s, result);
return result;
}
}

[@archygupta]

Java Code:
class Solution {
Map < String, List < String >> dp = new HashMap();
public List < String > wordBreak(String s, List < String > wordDict) {
if (dp.containsKey(s))
return dp.get(s);
List < String > result = new ArrayList();
for (String w: wordDict) {
if (s.length() >= w.length() && s.substring(0, w.length()).equals(w)) {
if (w.length() == s.length()) {
result.add(w);
} else {
List < String > tmp = wordBreak(s.substring(w.length()), wordDict);
for (String t: tmp) {
result.add(w + " " + t);
}
}
}
}
dp.put(s, result);
return result;
}
}

[@sonalisinha325]

it would be great if you clearly dry the recursive solution instead of just writing random things