Answer: Facebook SDE Interview Question 2023-March | Dynamic Programming & Backtracking

Solution for Question 1: Word Break II Approach: Memoized Depth First Search (DFS) Because we need to return ALL possible valid sentences, this is fundamentally a Backtracking / DFS problem. However, pure backtracking will explore the same sub-strings repeatedly, causing an exponential explosion in time complexity. To heavily optimize this, we must use Memoization (Top-Down Dynamic Programming). We maintain a HashMap where the Key is the remaining substring, and the Value is the List<String> containing all valid sentence endings generated ...