memo DFS 11ms no TLE


  • 0
    D

    idea is same as the bfs one: https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/15

    DFS perform very well for "true" results. But in "false" cases it will traverse the whole tree.

    Prune the visited false branches will help.
    Idean came from work break 2: https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs

    public boolean wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[] memo = new boolean[n + 1];
        for(int i = 0; i <= n; ++i) memo[i] = true;
        return dfs(memo, s, wordDict, 0, n);
    }
    public boolean dfs(boolean[] memo, String s, Set<String> dict, int start, int n) {
        if (memo[start] == false) return false;
        if(start == n) return true;
        for(int i = start + 1; i <= n; ++i) {
            if(dict.contains(s.substring(start, i)) &&
                dfs(memo, s, dict, i, n))
                return true;
        }
        memo[start] = false;
        return false;
    }

Log in to reply
 

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