Java beating 95.13% with explanation: DFS + memoization to avoid TLE


  • 4

    Basically the idea is to use a boolean array to avoid repeated computation.
    boolean[] invalid = new boolean[s.length()+1]
    invalid[i] means whether s.substring(i) is "not breakable"
    The helper function will return a boolean value whether the substring is "breakable" or not.
    For each call to helper function, denote current substring as [left, s.length()). Iterate right pointer i from left+1 to s.length(). If [left, i) can be found in the dict, and [i, s.length()) is "breakable", then the whole [left, s.length()) is "breakable".

     /**
     * Leetcode 140. Word Break II.
     * https://leetcode.com/problems/word-break-ii/
     * Keyword: DFS, backtracking
     *
     * @param s        string to break
     * @param wordDict word dictionary
     * @return all the possible ways to break the string into words in the dictionary
     */
    public List<String> wordBreak2(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<>();
        wordBreak2(s, 0, wordDict, "", new boolean[s.length() + 1], res);
        return res;
    }
    
    /**
     * Helper function for Leetcode 140. Word Break II.
     *
     * @param s        string to break
     * @param left     start point
     * @param wordDict dictionary
     * @param prev     previous word found
     * @param invalid  invalid[i] means whether [i, s.length()) is unbreakable
     * @param res      list to store results
     * @return true if s.substring(left) is breakable.
     */
    private boolean wordBreak2(String s, int left, Set<String> wordDict, String prev, boolean[] invalid, List<String> res) {
        // Base case: successfully moved to the end, add result to the list.
        if (left == s.length()) {
            res.add(prev.trim());
            return true;
        }
        // whether s.substring(left) is breakable
        boolean possible = false;
        // iterate the pointer from left+1 to the end, find whether [left, i) is valid
        for (int i = left + 1; i <= s.length(); i++) {
            // if s.substring(i) is unbreakable, continue
            if (invalid[i]) {
                continue;
            }
            String sub = s.substring(left, i);
            // if substring [left,i) is valid, move on and break from i
            if (wordDict.contains(sub)) {
                boolean flag = wordBreak2(s, i, wordDict, prev.concat(" ").concat(sub), invalid, res);
                // as long as at least one valid substring [i, end), possible is true
                possible = flag || possible;
            }
        }
        // update invalid array
        invalid[left] = !possible;
        return possible;
    }

Log in to reply
 

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