(Uber Phone interview) string pattern matching

  • 0

    The matching should cover the entire input string (not partial).
    The function prototype should be:

    bool isMatch(String str, String patter)
    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

  • 0

    a{1,3} means aaa, the right } is exclusive

  • 0

    @daniel.w.1 Do you mean that a{1,3} means that count of a's could be 1, 2 or 3, e. g a, aa, aaa is valid in this case? Thanks

  • 0

    @elmirap only 'a' and 'aa' are valid, because the right parenthesis is exclusive. a{1,3} essentially means 'a' can be repeated from index 1 to index 2, cannot be repeated at index 3 because right parenthesis is exclusive.

  • 0

    @daniel.w.1 What happens if pattern is a{4,5} b{1,2} ? Could you specify valid string for this pattern?
    Is it aaaab valid? Also could exist a pattern a{1,3}a?

  • 0

    @elmirap I have to ask the original problem poster, get back to u soon

  • 0

    @daniel.w.1 thanks I will be waiting for your clarification

  • 0

    @elmirap I think a{4,5} means aaaa, and a{1,2} means a

  • 0

    @moooc Is it possible to have a{1,3}a ? What do you think?

  • 0

    @elmirap : if a{4,5} means aaaa then what is the difference between a{1,5} and a{4,5

  • 0

    Simple backtracking based pattern recognition solution

    class Solution:
        def UBER_patternMatching(self, str, pat):
            :type str: string
            :type pat: string
            :rtype: bool
            if not pat:
                return not str
            minReps = 1
            maxReps = 1
            closeBraces = 0
            char = pat[0]
            if len(pat) > 1:
                if pat[1] == '{':
                    closeBraces = pat.find('}')
                    rangeSubstr = pat[2:closeBraces]
                    leftStr, rightStr = rangeSubstr.split(',')
                    maxReps = int(rightStr)
                    minReps = int(leftStr)
                    # print(minReps, maxReps)
            cntr = 0
            while cntr < minReps:
                if str[cntr] != char:
                    return False
                cntr += 1
            newStr = str[minReps:]
            newPat = pat[closeBraces+1:]
            if maxReps > minReps:
                diff = maxReps - minReps
                for i in range(0, diff):
                    newPatDiffed = char*i + newPat
                    # print(newPatDiffed, newStr)
                    success = self.UBER_patternMatching(newStr, newPatDiffed)
                    if success:
                        return True
                return False
                return self.UBER_patternMatching(newStr, newPat)

Log in to reply

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