Why is my JAVA solution so slow? Thanks a lot!


  • 0
    M
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null) return false;
    	  return helper(s, wordDict, new HashMap<String, Boolean>());      
        }
        private boolean helper(String s, Set<String> wordDict, Map<String, Boolean> visitedWords) {
        	if (wordDict.contains(s)) return true;
        	if (s.length() == 1) return false;
        	if (visitedWords.containsKey(s)) return visitedWords.get(s);
        	for (int i = 1 ; i < s.length() ; i++) {
        	    boolean prefixResult = wordDict.contains(s.substring(0,i)); 
        	    if (!prefixResult) {
        	        continue;
        	    }
        	    String suffix = s.substring(i);
        		boolean suffixResult = visitedWords.containsKey(suffix) ?  visitedWords.get(suffix) : helper(suffix, wordDict, visitedWords);
        		visitedWords.put(s, prefixResult && suffixResult);
        		if(prefixResult && suffixResult) {
        		    return true;
        		}
        	}
        	return false;
        }
    }

Log in to reply
 

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