Answer: LinkedIn OA Question 2024 May | Dynamic Programming | on-campus

Solution: Word Break — Bottom-Up Dynamic Programming Approach We use Bottom-Up DP. Define dp[i] as true if the substring s[0..i-1] can be segmented using words from the dictionary. Base case: dp[0] = true — an empty string is always segmentable. Transition: For each index i, check all previous positions j. If dp[j] is true and s[j..i-1] is in the dictionary, then dp[i] = true. Store the dictionary in a HashSet for O(1) lookups. Algorithm Walkthrough Add all words in wordDict ...