java solution BFS


  • 0
    2
    class Solution {
        public boolean checkValidString(String s) {
            Set<Integer> set = new HashSet<>();
            set.add(0);
            for (int i = 0; i < s.length(); i++) {
                Set<Integer> next = new HashSet<>();
                int[] increment;
                if (s.charAt(i) == '(') {
                    increment = new int[] {1};
                } else if (s.charAt(i) == ')') {
                    increment = new int[] {-1};
                } else {
                    increment = new int[] {1, 0, -1};
                }
                for (int j : set) {
                    for (int k : increment) {
                        int l = j + k;
                        if (l >= 0) {
                            next.add(l);
                        }
                    }
                }
                set = next;
            }
            return set.contains(0);
        }
    }
    

Log in to reply
 

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