JAVA accepted backtracking with memorization, curious about faster Algorithms.


  • 1
    S

    At first look it's not hard to see backtracking is suitable for this problem. Although I know there will be lots of duplicate cases i still implemented pure backtracking first and without surprising got TLE......

    An intuitive optimization is Memorization, I added it and got accepted.

     public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new LinkedList<String>();
        if (s == null || s.length() == 0 || wordDict.size() == 0) return result;
        return getBreaks(s, wordDict, 0, new List[s.length()]);
    }
    
    // memo[i] stores the break result of s.substring(i + 1)
    public List<String> getBreaks(String s, Set<String> wordDict, int pos, List<String>[] memo)
    {
        List<String> result = new LinkedList<String>();
        
        if (pos == s.length())
        {
            result.add("");
            return result;
        }
        
        for (int index = pos; index < s.length(); index++)
        {
            String curStr = s.substring(pos, index + 1);
            if (wordDict.contains(curStr))
            {
                List<String> next = null;
                // if we didn't break s.substring(index + 1) before, just break it and store the result
                if (memo[index] == null) {
                    next = getBreaks(s, wordDict, index + 1, memo);
                    memo[index] = next;
                }
                // if we have the break result, just use it
                else next = memo[index];
                
                for (String str : next)
                {
                    if (!str.equals(""))
                        result.add(curStr + " " + str);
                    else result.add(curStr);
                }
            }
        }
        return result;
    }
    

    And I notice that there are four "peaks" in the "Accepted Solutions Runtime Distribution", so I guess that means there are four major algorithms used by people here. Mine lies in the second from left, so one faster algorithm is expected. I'm so curious about what's that. Anyone's solution get there? Thanks in advance!


Log in to reply
 

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