DFS method to solve this problem


  • 0
    Q
    public class Solution {
    private boolean[] mark;
    private int len;
    public boolean wordBreak(String s, Set<String> dict) {
        //  use stack    optimization 150ms
        if (dict.contains(s)) return true;
        len = s.length();
        mark = new boolean[len + 1];
        java.util.LinkedList<Integer> stack = new java.util.LinkedList<Integer>();
        stack.push(0);
        while (!stack.isEmpty()) {
            int l = stack.pop();
            mark[l] = true;
            for (int r = l + 1; r <= len; r++) {
                if (dict.contains(s.substring(l, r)) && !mark[r]) {
                    if (r == len) return true;
                    stack.push(r);
                }
            }
        }
        return false;
        */
        
        
        /*
        // DFS  147ms
        if (dict.contains(s)) return true;
        len = s.length();
        mark = new boolean[len + 1];
        dfs(s, 0, dict);
        return mark[len];
    }
    private void dfs(String s, int l, Set<String> dict) {
        mark[l] = true;
        for (int r = l + 1; r <= len; r++) {
            if (dict.contains(s.substring(l, r)) && !mark[r]) {
                if (r == len) {
                    mark[r] = true;
                    return;
                }
                dfs(s, r, dict);
            }
        }
    }

Log in to reply
 

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