Onsite Interview Reflection: Regex Matching - With detailed solution and video

justin · November 5, 2019, 2:36pm

Hey everyone! Yesterday we worked through a Leetcode hard that a fellow was asked in a technical interview. Check out the problem, my solution, and our video recording of the group session!

Problem

Video

Solution

github.com

JustinHoyt/interview-practice/blob/master/leetcode/10_Regular_Expression_Matching.py

from typing import Dict


class Solution:
    def is_match_rec(self, string: str, pattern: str, string_idx: int,
                     pattern_idx: int, memo: Dict) -> bool:
        self.print_current_state(string, pattern, string_idx, pattern_idx)
        key = (string_idx, pattern_idx)
        if key in memo:
            return memo[key]
        is_zero_or_many = pattern_idx + 1 < len(pattern) and pattern[pattern_idx + 1] == "*"
        if string_idx >= len(string) and pattern_idx >= len(pattern):
            return True
        if string_idx >= len(string) and pattern_idx == len(pattern) - 2 and is_zero_or_many:
            return True
        if (string_idx >= len(string) or pattern_idx >= len(pattern)) and not is_zero_or_many:
            return False

        if is_zero_or_many:
            # evaluate pattern index, and move string idx

This file has been truncated. show original

The solution has an interactive print statement that will visually point at where the indices are for the strings to make understanding the solution a bit easier. All you have to do is press enter to “step forward”.