Java DP recursive approach beats 95%

  • 0
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
             Set<String> hs = new HashSet<>(wordDict);
            Map<String, Boolean> map = new HashMap<>();
            return find(s, hs, 0, 0, map);
        public boolean find(String s, Set<String> hs, int left, int right, Map<String, Boolean> map){
             if(right > s.length() && right-left == 1) return true;
            if(right > s.length()) return false;
            String str = s.substring(left, right);
            if(map.containsKey(str)) return map.get(str);
            boolean rvalue;
            	rvalue = find(s, hs, left, right+1, map) || find(s, hs, right, right+1, map);
                rvalue = find(s, hs, left, right+1, map);
            map.put(str, rvalue);
            return rvalue;

  • 0

    Can you please add some explanation for this solution? It will help to understand the approach a lot.

Log in to reply

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