String Pattern Matching

Image placeholder 9899

(This question has been seen in the interviews of the following companies: Uber)

The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(String str, String pattern)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a{1,3}") → true
isMatch("aaa","a{1,3}") → false
isMatch("ab","a{1,3}b{1,3}") → true
isMatch("abc","a{1,3}b{1,3}c") → true
isMatch("abbc","a{1,3}b{1,2}c") → false
isMatch("acbac","a{1,3}b{1,3}c") → false
isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true
In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} -> a occurs 1 or 2 times.


public boolean match(String str, String pattern) {
        int occurLower = 0, occurUpper = 0;
        char prev = '\0';
        int i = 0, j = 0;

        while(j < pattern.length()) {
            char c = i == str.length() ? '\0': str.charAt(i);
            if (occurUpper == 0 || prev == pattern.charAt(j) || (c != prev && occurLower <= 0)) {
                String range = j + 1 < pattern.length() && pattern.charAt(j + 1) == '{' ?
                        pattern.substring(j + 2, pattern.indexOf('}', j + 2)): "";
                int[] r = getRange(range);
                occurLower = prev == pattern.charAt(j) ? occurLower + r[0] : r[0];
                occurUpper = prev == pattern.charAt(j) ? occurUpper + r[1] : r[1];
                prev = pattern.charAt(j);
                j = range.isEmpty() ? j + 1: pattern.indexOf('}', j + 2) + 1;
            }
            if (c == prev) {
                occurLower--;
                occurUpper--;
                i++;
            } else if (occurLower > 0) {
                return false;
            }
        }
        while(i < str.length()) {
            if(str.charAt(i) != prev || occurUpper == 0) return false;
            else {
                occurUpper--;
                i++;
            }
        }
        return true;
    }

    private int[] getRange(String b) {
        if(b.isEmpty()) return new int[]{1,1};
        int comma = b.indexOf(',');
        return new int[]{
                Integer.parseInt(b.substring(0, comma)),
                Integer.parseInt(b.substring(comma + 1)) - 1
        };
    }



Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.