DFS to solve this problem


  • 0
    Q

    Many elegent algorithms such as DP and BFS are provided in the forum, and I want to show you the DFS method, which is also a good method to solve this problem.

     public class Solution {
        private boolean[] mark;
        private int len;
        public boolean wordBreak(String s, Set<String> dict) {
            // DFS 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;
       }
    }

Log in to reply
 

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