How to memoise recursive solution to make it dynamic?


  • 0
    M

    Here is my solution,

    I would like to find a way to memoise the recursive calls but can't see how that's possible. This could be entirely attributable to my lack of imagination :( Any hints?

        private String s;
        private Set<String> dict;
        private ArrayList<String> sentences;
    
        public ArrayList<String> wordBreak(String s, Set<String> dict) {
            sentences = new ArrayList<String>();
            if (dict == null || s == null) {
                return sentences;
            }
            if (dict.isEmpty() || s.isEmpty()) {
                return sentences;
            }
    
            if (!checkLetters(s, dict)) {
                return sentences;
            }
            this.s = s;
            this.dict = dict;
            getSentence(0, new StringBuffer(), new StringBuffer());
            return sentences;
        }
    
        private void getSentence(int index, StringBuffer strBuf, StringBuffer remainder) {
            if (index > s.length() - 1) {
                if (remainder.toString().isEmpty()) {
                    sentences.add(strBuf.toString());
                }
                return;
            }
            remainder.append(s.charAt(index));
            index++;
            if (dict.contains(remainder.toString())) {
                StringBuffer newBuf = new StringBuffer(strBuf.toString());
                if (strBuf.toString().isEmpty()){
                    strBuf.append(remainder.toString());
                }else{
                    strBuf.append(" ").append(remainder.toString());
                }
                getSentence(index, strBuf, new StringBuffer());
                getSentence(index, newBuf, remainder);
            } else {
                getSentence(index, strBuf, remainder);
            }
        }
    
        //hack to pass the test with tons of "a" in the string and dictionary. Ends up being  exponential time with all the branching :(
    
        private boolean checkLetters(String s, Set<String> dict) {
            int strChars = 0;
            int dictChars = 0;
            for (int i = 0; i < s.length(); i++) {
                int tmpNum = s.charAt(i) - 97;
                strChars = strChars | (1 << tmpNum);
            }
            for (String word : dict) {
                for (int i = 0; i < word.length(); i++) {
                    int tmpNum = word.charAt(i) - 97;
                    dictChars = dictChars | (1 << tmpNum);
                }
            }
            int result =(strChars & dictChars);
            return result ==strChars;
        }
    
    }

  • 3
    L

    Here is my code using memoization.

    The main function does not do much: examines some of the border cases, create a Map memo for the memoization, and call the recursive function. I use sets everywhere so that I don't have to care myself about duplicates. I convert the solution into an ArrayList at the end.

    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> sentences = new ArrayList<String>();
            
        if (s == null || s.length() == 0) 
            return sentences;
            
        Map<String,Set<String>> memo = new HashMap<String,Set<String>>();
        wordBreak(s,memo,dict);
        sentences.addAll(memo.get(s));
        return sentences;
    }
    

    The recursive function works this way:

    1. if wordbreak of s has already been memoized, do nothing.
    2. if s is in the dictionnary, add s to the set of solutions.
    3. if s is only one character long, we're done.
    4. I split s into left and right for all the possible splits. If left and right have already been memoized, that perfect, otherwise I recursively call wordBreak. Finally I merge the sentences of leftSet and rightSet

    The key point here is to notice that if leftSet is empy, then there won't be any sentence for this split, so their is no need to make the recursive call on right. This is why there are the 3 tests with the continue statement. If you remove them, the the algorithm will TLE.

    public void wordBreak(String s, Map<String,Set<String>> memo, Set<String> dict) {
    if (memo.containsKey(s)) 
        return;
    
    Set<String> res = new HashSet<String>();
    if (dict.contains(s))
        res.add(s);
    if (s.length() == 1) {
        memo.put(s,res);
        return;
    }
    for (int i = 1 ; i < s.length() ; i++) {
        String left = s.substring(0,i);
        String right = s.substring(i);
        if (memo.containsKey(left) && memo.get(left).isEmpty() || memo.containsKey(right) && memo.get(right).isEmpty()) {
            continue;
        }
        if (!memo.containsKey(left)) {
            wordBreak(left,memo,dict);
            if (memo.get(left).isEmpty()) {
                continue;
            }
        }
        if (!memo.containsKey(right)) {
            wordBreak(right,memo,dict);
            if (memo.get(right).isEmpty()) {
                continue;
            }
        }
        Set<String> leftSet = memo.get(left);
        Set<String> rightSet = memo.get(right);
        if (!rightSet.isEmpty() && !leftSet.isEmpty()) {
            for (String rightWords : rightSet) {
                for (String leftWords : leftSet) {
                    res.add(leftWords + " " + rightWords);
                }
            }
        }
    }
    memo.put(s,res);
    }
    

  • 0
    P

    I believe my code is more concise and efficient than yours but it can't pass the large case. This is only because your code above can detected invalid character ( the 'b' in 'a.......b' ) better. This is a very rare case and happens to pass the large test case. The test case is ill designed anyway.

    public ArrayList<String> wordBreak(String s, Set<String> dict) {

    	if (s == null || s.isEmpty())
    		return new ArrayList<String>();
    
    	Map<Integer, ArrayList<String>> cache = new HashMap<Integer, ArrayList<String>>();
    	cache.put(0, new ArrayList<String>());
    	cache.get(0).add("");
    
    	for (int i = 1; i <= s.length(); i++) {
    
    		Iterator<Integer> it = cache.keySet().iterator();
    		ArrayList<String> lst = new ArrayList<String>();
    
    		while (it.hasNext()) {
    			int j = it.next();
    
    			String tmp = s.substring(j, i);
    			if (dict.contains(tmp)) {
    				String newAdd = "";
    				if (j == 0)
    					newAdd = tmp;
    				else
    					newAdd = " " + tmp;
    
    				for (String str : cache.get(j)) {
    					lst.add(str + newAdd);
    				}
    			}
    		}
    
    		if (!lst.isEmpty())
    			cache.put(i, lst);
    	}
    
    	return cache.containsKey(s.length()) ? cache.get(s.length())
    			: new ArrayList<String>();
    }

  • 0
    S

    @peking3, Could you please post it as an answer? When you do it, please format your code correctly. Thanks.


Log in to reply
 

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