Word break 2

Leetcode: https://leetcode.com/problems/word-break-ii/ Editorial: https://leetcode.com/problems/word-break-ii/discuss/44167/My-concise-JAVA-solution-based-on-memorized-DFS

Create valid sentences from the initial string and the word directory provided.

Solution Concepts

Concept 1: recursion

If the word is "catsdogsgoats" and the word dictionary is "cats", "cat", dogs" and "goats" Then we need to check for all words which are valid and maybe a starting word. For example the word "cat" is a starting word, same as "cats" So the word can be any word of the dictionary, we do not know.

1. Check for all the words in the dictionary, we don't know when to stop
2. When I get the first word, I need to search the rest of the string in a similar manner

I was thinking I will create a trie like data structure and then keep a map of stuff. Too complicated.

The solution is to observe recursion and manipulation, in step 2 I said "do the same thing for the rest of the string" that's sound like a recursion

So get a starting word and call the function f(remaining word) The return will be a list of valid sentences of remaining word

So the resultant will be word + each of the valid sentences of the remaining word

So loop through f(remaining words) and prepend the first word in each case

Brilliant

1. get the first valid word in the sentence
2. recursion on the remaining string

Concept 2: manipulation

So we needed to construct sentence like word1word2word3 So he checked if word.isEmpty() ? "": " " + word

Good solution, but we can just do trim at the end, not a great use case but still good tool to have.