Java DP recursive approach beats 95%


  • 0
    S
    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;
            if(hs.contains(str)){
            	rvalue = find(s, hs, left, right+1, map) || find(s, hs, right, right+1, map);
            }
            else{
                rvalue = find(s, hs, left, right+1, map);
            }
            map.put(str, rvalue);
            return rvalue;
        }
    }
    

  • 0
    S

    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.