Memoization Java Solution (Controlled Recursion) With Explanation


  • 0
    S

    The recursive solution, I hope, is fairly straightforward. Search the string s until a prefix is found, then do the same thing again. Stop when a valid prefix, a word that is the dictionary, is found which ends with the last character in s. That is, the valid prefix is just the current string s passed into RwordBreak. (Note: I also stop when I find the next prefix to search is identical to the one just found). To prevent the same sub-problem being run many times, check to see if it was already processed before processing any sub-problem.
    For example, sub-problems occurring many times can happen when strings in the dictionary overlap. Such as, "bbbb" and "bb" and then in the string s there is something like "bbbbXXXXXX". Suppose the "XXXXXX" sub-problem fails to yield a result (done = true), when "bbbb" is found to be a valid prefix, then when "bb" is found to be a valid prefix, if it get's to the point where it needs to process "XXXXXX" it will be doing wasteful processing (this would happen when "bb" is again found to be a valid prefix in the new prefix "bbXXXXXX").

    public class Solution {
    
        public boolean wordBreak(String s, Set<String> wordDict) 
        {
             HashSet<String> memo = new HashSet<String>();
             if(wordDict.contains(s))
                 return true;
             return RwordBreak(s,wordDict, memo);
        }
       
        private boolean RwordBreak(String s,Set<String> wordDict, HashSet<String> memo)
        {
            boolean done = false;
            for(int i=s.length(); i>-1 && !done; i--)
            {
                String tmp = s.substring(0,i);
                if(!memo.contains(tmp))
                {
                    if(wordDict.contains(tmp))
                    {
                        String tmp2 = s.substring(i);
                        
                        if(i==s.length() || tmp.equals(tmp2))
                        {
                            done = true;
                        }
                        else
                        {
                             done = RwordBreak(tmp2,wordDict,memo);
                        }
                    }
                }
                else
                {
                    break;
                }
                
            }
            
            memo.add(s);
            return done;
        }
    }
    

Log in to reply
 

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