Day 67: Regular Expression Matching

Day 67 — Regular Expression Matching

Coding problem

Solution outline (coding)

• 2D DP: dp[i][j] = does s[0:i) match p[0:j) with * and . rules.
• * = zero or more of preceding char; try match and skip patterns.
• Base cases for empty string vs pattern.

Time complexity: O(m · n) — string and pattern lengths.

Space complexity: O(m · n) table; can optimize to O(n) rows.

class Solution:
  def isMatch(self, s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(2, n + 1):
      if p[j - 1] == '*':
        dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
          dp[i][j] = dp[i - 1][j - 1]
        elif p[j - 1] == '*':
          dp[i][j] = dp[i][j - 2]
          if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
            dp[i][j] = dp[i][j] or dp[i - 1][j]
    return dp[m][n]


# Input:  s = "aa", p = "a*"
# Output: True

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
pattern(text_id, s, p). BigQuery: for simplified regex patterns, show how far you can go using SQL functions vs external engines and prototype a limited matcher.

Tables implied by the prompt:

• pattern(text_id, s, p)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map DP to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT text_id, REGEXP_CONTAINS(s, r'^a*b*$') AS simple_match FROM pattern LIMIT 100;