Accepted Java Recursive Solution with Duo-DP


  • 0
    D

    Trivial recursive solution with single DP will get over time error.
    The trick is to use a set to record unbreakable strings to avoid duplicated computation.

    public class Solution {
            public HashMap<String,ArrayList<String>> stringToWords;
            public Set<String> unbreakable;
    
            public void wordBreak2(String s,Set<String> dict)
            {
                if(stringToWords.containsKey(s)||unbreakable.contains(s))
                    return;
                for(String word:dict)
                {
                    if(s.equals(word))
                    {
                        ArrayList<String> bufferList=new ArrayList<String>();
                        if(stringToWords.containsKey(word))
                            bufferList=stringToWords.get(word);
                        bufferList.add(s);
                        stringToWords.put(word,bufferList);
                    }
                    else if(s.indexOf(word)==0)
                    {
                        String nextString=s.replaceFirst(word,"");
                        if((!stringToWords.containsKey(nextString))&&(!unbreakable.contains(nextString)))
                            wordBreak2(nextString,dict);
                        if(stringToWords.containsKey(nextString))
                        {
                            ArrayList<String> bufferList=new ArrayList<String>();
                            if(stringToWords.containsKey(s))
                                bufferList=stringToWords.get(s);
                            for(String sTemp:stringToWords.get(nextString))
                            {
                                bufferList.add(word+" "+sTemp);
                            }
                            stringToWords.put(s,bufferList);
                        }
                        else
                            unbreakable.add(nextString);
                    }
                }
            }
    
            public List<String> wordBreak(String s, Set<String> dict) {
                ArrayList<String> result=new ArrayList();
                unbreakable=new HashSet<String>();
                if(s.length()==0||dict.size()==0)
                {
                    result.clear();
                    return result;
                }
                stringToWords=new HashMap<String,ArrayList<String>>();
                if(stringToWords.containsKey(s))
                    return stringToWords.get(s);
                else
                {
                    wordBreak2(s,dict);
                    if(stringToWords.containsKey(s))
                        return stringToWords.get(s);
                    else
                    {
                        result.clear();
                        return result;
                    }
                }
            }
        }

Log in to reply
 

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