Share my Java solution


  • 0
    D

    The main idea is try to match s with no wildcard and store each wildcard matching. When a mismatch occurs, we start to backtrack wildcard stack and try to match s with the most recent wildcard.

    class WildcardRecord {
        int idxS;
        int idxP;
        char matchingChar;
        public WildcardRecord(int idxS, int idxP, char matchingChar) {
            this.idxS = idxS;
            this.idxP = idxP;
            this.matchingChar = matchingChar;
        }
    }
    
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int sLen = s.length();
        int pLen = p.length();
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int i = 0; int j = 0;
        LinkedList<WildcardRecord> stack = new LinkedList<WildcardRecord>();
        while (i < sLen || j < pLen) {
            if (j < pLen - 1 && cp[j + 1] == '*') {
                // wildcard found
                WildcardRecord wildRec = new WildcardRecord(i, j + 2, cp[j]);
                j += 2;
                stack.push(wildRec);
            }
            else if (i == sLen) return false;
            else if (j == pLen || cp[j] != '.' && cs[i] != cp[j]) {
                // backtrack
                while (!stack.isEmpty()) {
                    WildcardRecord wildRec = stack.peek();
                    if (wildRec.matchingChar == '.' || cs[wildRec.idxS] == wildRec.matchingChar) {
                        wildRec.idxS++;
                        i = wildRec.idxS;
                        j = wildRec.idxP;
                        break;
                    }
                    else {
                        stack.pop();
                    }
                }
                if (stack.isEmpty()) return false;
            }
            else {
                // plain match
                i++; j++;
            }
        }
        return true;
    }

Log in to reply
 

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