Blind 75
Word Break
- Problem
- LC 139
- Category
- DP
- File
- blind75_LC139WordBreak.java
- Path
- pkg5leetcode/blind75/blind75_LC139WordBreak.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC139WordBreak.java
- Approach
- DP dp[i]=true if prefix s[0..i) can be segmented.
- Complexity
- Time O(n^2 * words), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Word Break | LC 1395 * APPROACH: DP dp[i]=true if prefix s[0..i) can be segmented.6 * COMPLEXITY: Time O(n^2 * words), Space O(n)7 */8import java.util.*;9 10public class blind75_LC139WordBreak {11 static boolean wordBreak(String s, List<String> wordDict) {12 Set<String> dict = new HashSet<>(wordDict);13 boolean[] dp = new boolean[s.length() + 1];14 dp[0] = true;15 for (int i = 1; i <= s.length(); i++)16 for (int j = 0; j < i; j++)17 if (dp[j] && dict.contains(s.substring(j, i))) {18 dp[i] = true;19 break;20 }21 return dp[s.length()];22 }23 24 public static void main(String[] args) {25 check(wordBreak("leetcode", Arrays.asList("leet", "code")), "case1");26 check(!wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")), "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}