LeetCode 139 - Word Break

Prompt: Given a string with no spaces and a list of words, is it possible to break the strings in separate words that exist in the list of words.

Example:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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.

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Solution: This is likely a DFS problem. A simple solution would be a DFS function to loop through all existing words in the word list and see if the current string starts with any existing words.
If there are words that exist in the beginning of the current string, then remove the word from the start of the current string and pass it on to the next DFS.
If there are no existing words that begin on the current string, then the word break is not possible.
The base case for DFS is when the current string is empty because we kept removing words from the current string when we passed it to its next DFS.
Finally, in order to avoid repeating certain paths that were already searched, we can have a dictionary that remembers DFS to certain words and returns a True or False at the end.