Backtracking Approach Using Double-ended Queue


  • 0
    O

    My approach is to match character by character. When [star] is encountered, greedily match to the end. If there are still more regex tokens, backtrack by recovering previously matched input tokens until the all characters matched by the * have been recovered. Then discard all characters in input until the next character in the regex is encountered. Then reattempt matching, decreasing the backtracking depth.

    However the code below is incomplete. It fails case s = "sayomarbrv", p = "s.*rv"
    Does the approach make sense?

    import java.util.*;
    public class Solution {
        public boolean isMatch(String s, String p) {
            Deque<Character> inputDeque = new ArrayDeque<Character>();
            for (char c : s.toCharArray()) {
                inputDeque.add(c);
            }
            Deque<Character> regexDeque = new ArrayDeque<Character>();
            for (char c : p.toCharArray()) {
                regexDeque.add(c);
            }
            
            boolean any = false;
            char curr = '\u0000';
            Deque<Integer> depthDeque = new ArrayDeque<Integer>();
            Deque<Character> buffer = new ArrayDeque<Character>();
            while (!regexDeque.isEmpty()) {
                if (inputDeque.isEmpty()) {
                    return false;
                }
                
                char c = regexDeque.pop();
                if (c == '.') {
                    any = true;
                } else if (c == '*') {
                    depthDeque.push(inputDeque.size());
                    buffer.clear();
                    while (!inputDeque.isEmpty() && (any || inputDeque.peek() == curr)) {
                        buffer.push(inputDeque.pop());
                    }
                    
                    if (!regexDeque.isEmpty() && inputDeque.isEmpty()) { // If there's still regex but no input
                        // Push back till next regex bDepth's occurrence of next regex token is encoutered.
                        int count = 0;
                        while (!buffer.isEmpty()) {
                            inputDeque.push(buffer.pop());
                            count++;
                            
                            if (count >= depthDeque.peek()) {
                                int bDepth = Math.max(0, depthDeque.peek() - 1);
                                depthDeque.pop(); depthDeque.push(bDepth);
                                break;
                            }
                        }
                        
                        while (!inputDeque.isEmpty() && inputDeque.peek() != regexDeque.peek()) {
                            inputDeque.pop();
                        }
                        
                        any = false;
                    }
                } else {
                    curr = c;
                    any = false;
                }
                
                if (!inputDeque.isEmpty() && (any || inputDeque.peek() == curr)) {
                    inputDeque.pop();
                } else {
                    // if (depthDeque.peek() > 0) {
                    //     while (!inputDeque.isEmpty() && inputDeque.peek() != curr) {
                    //         inputDeque.pop();
                    //     }
                    //     if (!inputDeque.isEmpty()) {
                    //         inputDeque.pop();
                    //     }
                    //     while (!inputDeque.isEmpty() && inputDeque.peek() != curr) {
                    //         inputDeque.pop();
                    //     }
                    //     bDepth--;
                    // }
                }
                
                //depthDeque.pop();
            }
            
            return inputDeque.isEmpty();
        }
    }

Log in to reply
 

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