package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/word-break/
 */
public class Problem139 {
    public boolean wordBreak(String s, Set<String> dict) {
        return wordBreak(s, dict, new HashSet<>());
    }

    private boolean wordBreak(String s, Set<String> dict, Set<String> memo) {
        for (String d : dict) {
            if (s.equals(d)) {
                return true;
            }
            if (memo.contains(s)) {
                return false;
            }
            if (s.startsWith(d)) {
                boolean found = wordBreak(s.substring(d.length()), dict, memo);
                if (found) {
                    return true;
                }
            }
        }
        memo.add(s);
        return false;
    }
}

@@ -38,16 +38,39 @@
 ashSet;%0A
+import java.util.List;%0A
 import j
@@ -194,34 +194,35 @@
 Break(String s, 
-Se
+Lis
 t%3CString%3E dict) 
@@ -215,17 +215,21 @@
 String%3E 
-d
+wordD
 ict) %7B%0A 
@@ -255,17 +255,21 @@
 reak(s, 
-d
+wordD
 ict, new
@@ -302,16 +302,23 @@
 private 
+static 
 boolean 
@@ -337,18 +337,19 @@
 ring s, 
-Se
+Lis
 t%3CString

Update problem 139