memo DFS 11ms no TLE

  • 0

    idea is same as the bfs one:

    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:

    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.