Just a straightforward method: memorized searching + DFS


  • 0
    S

    It's a little bit slower, I didn't use DP. It's easier for me to come up with this solution.

    private HashMap<String, Boolean> map = new HashMap<>();
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s.length() == 0) return true;
        if (map.containsKey(s)) return map.get(s);
        for (int i = 0; i <= s.length(); i++) {
            String prefix = s.substring(0, i);
            if (wordDict.contains(prefix)) {
                if (wordBreak(s.substring(i), wordDict)) {  
                    map.put(s, true);
                    return true;
                }
            }
        }
        map.put(s, false);
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.