mediumStringsPattern: Recursive
Recursive String Partitioning Solution
Problem Statement
Given a string s and a set of valid strings, determine all possible ways to partition s into valid strings, using a recursive approach to find all valid partitions.
Examples
Example 1:
Input:{"s":"catsanddog","wordDict":["cat","cats","and","sand","dog"]}
Output:[["cat","sand","dog"],["cats","and","dog"]]
Explanation: The input string 'catsanddog' can be partitioned into valid strings as 'cat' + 'sand' + 'dog' or 'cats' + 'and' + 'dog'.
Example 2:
Input:{"s":"pineapplepenapple","wordDict":["apple","pen","applepen","pine","pineapple"]}
Output:[["pine","apple","pen","apple"],["pineapple","pen","apple"],["pine","applepen","apple"]]
Explanation: The input string 'pineapplepenapple' can be partitioned into valid strings in three different ways, as shown in the output.
Constraints
- 1 <= s.length <= 14
- 1 <= wordDict.length <= 10^4
- All strings in wordDict have lengths between 1 and 7
- All characters in s and wordDict are lowercase English letters
Time: O(n^2) Space: O(n^2)
The optimized approach uses a recursive function with memoization to store the results of subproblems, reducing the time complexity to O(n^2) where n is the length of the input string. Additionally, using a HashSet to store the valid words allows for efficient lookup.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.