Word Break
Advanced Backtracking DSA practice problem on Onlearn.
Difficulty: hard.
Topics: What is the Word Break problem and how can it be solved using different algorithmic approaches?, Dynamic Programming, Recursion, Memoization, Hash Map, String Manipulation, Time Complexity, Space Complexity, Big O Notation, dynamic programming, trie, backtracking, hashing, recursion, Backtracking Constraints, Trie (Prefix Tree).
Word Break Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space separated sequence of one or more dictionary words. The same word in the dictionary may be reused multiple times in the segmentation. Note: You may assume the dictionary does not contain duplicate words. Input The first line contains a string s. The second line contains a list of strings wordDict, where each string is a word in the dictionary. Output Return true if s can be segmented, otherwise return false. Constraints 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique. Sample Input 1 Sample Output 1 Explanation: Return true because "leetcode" can be segmented as "leet code". Sample Input 2 Sample Output 2 Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you can reuse a dictionary word. Sample Input 3 Sample Output 3