139

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean ans = false;
        if(s == null || s.length() == 0) return ans;
        Set<String> dict = new HashSet<>(wordDict);
        return helper(s, dict);
    }

    Map<String, Boolean> checkedStr = new HashMap<>();
    private boolean helper(String s, Set<String> dict) {
        if(s.length() == 0) return true;
        if(dict.contains(s)) return true;
        if(checkedStr.containsKey(s)) return checkedStr.get(s);
        boolean ans = false;
        for(int i=1; i<s.length(); i++) {
            if(dict.contains(s.substring(0,i))) {
                boolean tmpAns = helper(s.substring(i), dict);
                checkedStr.put(s.substring(i), tmpAns);
                ans |= tmpAns;
            }
        }
        return ans;
    }
}