Word Break
Problem Description
Given a string s and a dictionary wordDict, return true if s can be segmented into space-separated words all in the dictionary.
Example 1:
Input: s="leetcode", wordDict=["leet","code"]
Output: true
Example 2:
Input: s="applepenapple", wordDict=["apple","pen"]
Output: true (apple+pen+apple)
Example 3:
Input: s="catsandog", wordDict=["cats","dog","sand","and","cat"]
Output: false
DE Shaw Tier 3 — LC 139.
DP O(n^2): dp[i] = can s[0..i-1] be segmented. For each i, check all j < i: dp[i] = dp[j] && wordDict has s[j..i-1]. Use a Set for O(1) word lookup.
Example Test Cases
Example 1
Input: ["leetcode",["leet","code"]]
Expected: true
Example 2
Input: ["applepenapple",["apple","pen"]]
Expected: true
Example 3
Input: ["catsandog",["cats","dog","sand","and","cat"]]
Expected: false
Example 4
Input: ["a",["b"]]
Expected: false
Run your code to see the results