Regular Expression Matching

🎯

Regular Expression Matching

hardDPGoogleFacebookAmazon

Imagine building a search engine that supports complex pattern queries with '.' and '*' wildcards, and you need to verify if a given text matches a pattern.

💡 This problem is a classic example of string dynamic programming involving pattern matching with special characters. Beginners often struggle because the pattern includes '.' and '*' which have special meanings, making naive matching tricky. Understanding how to break down the problem into subproblems is key.

📋

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Return true if s matches p, otherwise false.

1 ≤ s.length, p.length ≤ 1000s contains only lowercase English lettersp contains only lowercase English letters, '.' and '*'

💡

Example

Input"s = \"aa\", p = \"a\""

Outputfalse

Pattern 'a' does not match the entire string 'aa'.

Input"s = \"aa\", p = \"a*\""

Outputtrue

'*' means zero or more of the preceding element 'a'. So 'a*' can match 'aa'.

Input"s = \"ab\", p = \".*\""

Outputtrue

'.*' means 'zero or more (*) of any character (.)', so it matches 'ab'.

Input"s = \"aab\", p = \"c*a*b\""

Outputtrue

'c*' can match zero 'c's, 'a*' matches 'aa', and 'b' matches 'b'.

• Empty string s and empty pattern p → true
• Empty string s and pattern with only '*' (like 'a*') → true
• Pattern with '*' at the start (invalid pattern) → should handle gracefully
• String s with repeated characters and pattern with multiple '*' → correct matching

🔁

Why DP?

Why greedy fails:

A greedy approach fails because '*' can match zero or more of the preceding element, and choosing to match greedily early can prevent matching the rest of the string. For example, s='aab', p='c*a*b': greedily matching 'c*' as many times as possible fails, but matching zero 'c's works.

DP state:

dp[i][j] means whether the substring s[0..i-1] matches the pattern p[0..j-1]. True if matches, false otherwise.

Recurrence:dp[i][j] = (p[j-1] == s[i-1] or p[j-1] == '.') and dp[i-1][j-1] or (p[j-1] == '*' and (dp[i][j-2] or ((p[j-2] == s[i-1] or p[j-2] == '.') and dp[i-1][j])))

If current pattern char is normal or '.', match current chars and check previous substrings. If '*', either ignore the '*' and preceding char or use '*' to match current char if possible.

⚠️

Common Mistakes

Not handling '*' as zero occurrences properly

Incorrectly returns false when pattern can match empty string

✅ Always check dp[i][j-2] when '*' is encountered to represent zero occurrence

Confusing indices off-by-one in dp table

Index errors or wrong matches

✅ Remember dp[i][j] corresponds to s[:i] and p[:j], so s[i-1] and p[j-1] are current chars

Not iterating backwards in space optimized approach

Overwrites dp[j-2] before use, causing wrong results

✅ Iterate backwards over pattern indices when updating dp array

Assuming '.' matches zero characters

Incorrect matches when '.' is treated like '*'

✅ '.' matches exactly one character; only '*' allows zero or more

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and the complexity caused by '*' and '.' wildcards. It reveals overlapping subproblems that motivate DP.

Intuition

Try to match the string and pattern character by character recursively, handling '.' as any char and '*' as zero or more of the preceding element by branching into multiple recursive calls.

Algorithm

1. If pattern is empty, return true if string is also empty.
2. Check if first characters match (considering '.' wildcard).
3. If next pattern char is '*', recursively check two cases: zero occurrence or one/more occurrences.
4. Otherwise, move both pointers forward if first chars match.

💡 The recursion explores all ways '*' can match zero or more chars, which is conceptually simple but inefficient.

Recurrence:match(i,j) = (p[j] == s[i] or p[j] == '.') and match(i+1,j+1) or (p[j+1] == '*' and (match(i,j+2) or (first_match and match(i+1,j))))

</>

Code

def isMatch(s: str, p: str) -> bool:
    def dfs(i, j):
        if j == len(p):
            return i == len(s)
        first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
        if j + 1 < len(p) and p[j+1] == '*':
            return dfs(i, j+2) or (first_match and dfs(i+1, j))
        else:
            return first_match and dfs(i+1, j+1)
    return dfs(0, 0)

# Example usage:
if __name__ == '__main__':
    print(isMatch('aab', 'c*a*b'))  # True

Line Notes

def dfs(i, j):Defines recursive helper to match s[i:] with p[j:]

if j == len(p):If pattern exhausted, string must also be exhausted

first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')Check if current chars match or pattern is '.'

if j + 1 < len(p) and p[j+1] == '*':If next pattern char is '*', handle zero or more occurrences

return dfs(i, j+2) or (first_match and dfs(i+1, j))Try skipping '*' or consuming one char if matches

return first_match and dfs(i+1, j+1)If no '*', move both pointers if chars match

public class Solution {
    public boolean isMatch(String s, String p) {
        return dfs(s, p, 0, 0);
    }
    private boolean dfs(String s, String p, int i, int j) {
        if (j == p.length()) return i == s.length();
        boolean firstMatch = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            return dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));
        } else {
            return firstMatch && dfs(s, p, i + 1, j + 1);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("aab", "c*a*b")); // true
    }
}

Line Notes

public boolean isMatch(String s, String p)Entry point calling recursive helper

if (j == p.length()) return i == s.length();Pattern exhausted means string must be exhausted

boolean firstMatch = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')Check current char match or '.' wildcard

if (j + 1 < p.length() && p.charAt(j + 1) == '*')Handle '*' by branching recursion

return dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));Skip '*' or consume one char if matches

return firstMatch && dfs(s, p, i + 1, j + 1);No '*', move both pointers if match

#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
    bool dfs(const string& s, const string& p, int i, int j) {
        if (j == p.size()) return i == s.size();
        bool firstMatch = i < s.size() && (p[j] == s[i] || p[j] == '.');
        if (j + 1 < p.size() && p[j + 1] == '*') {
            return dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));
        } else {
            return firstMatch && dfs(s, p, i + 1, j + 1);
        }
    }
    bool isMatch(string s, string p) {
        return dfs(s, p, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("aab", "c*a*b") << endl; // true
    return 0;
}

Line Notes

bool dfs(const string& s, const string& p, int i, int j)Recursive helper matching s[i:] and p[j:]

if (j == p.size()) return i == s.size();Pattern exhausted means string must be exhausted

bool firstMatch = i < s.size() && (p[j] == s[i] || p[j] == '.')Check if current chars match or '.' wildcard

if (j + 1 < p.size() && p[j + 1] == '*')Handle '*' by branching recursion

return dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));Skip '*' or consume one char if matches

return firstMatch && dfs(s, p, i + 1, j + 1);No '*', move both pointers if match

function isMatch(s, p) {
    function dfs(i, j) {
        if (j === p.length) return i === s.length;
        const firstMatch = i < s.length && (p[j] === s[i] || p[j] === '.');
        if (j + 1 < p.length && p[j + 1] === '*') {
            return dfs(i, j + 2) || (firstMatch && dfs(i + 1, j));
        } else {
            return firstMatch && dfs(i + 1, j + 1);
        }
    }
    return dfs(0, 0);
}

// Example usage:
console.log(isMatch('aab', 'c*a*b')); // true

Line Notes

function dfs(i, j)Recursive helper matching s[i:] and p[j:]

if (j === p.length) return i === s.length;Pattern exhausted means string must be exhausted

const firstMatch = i < s.length && (p[j] === s[i] || p[j] === '.')Check if current chars match or '.' wildcard

if (j + 1 < p.length && p[j + 1] === '*')Handle '*' by branching recursion

return dfs(i, j + 2) || (firstMatch && dfs(i + 1, j));Skip '*' or consume one char if matches

return firstMatch && dfs(i + 1, j + 1);No '*', move both pointers if match

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each '*' can branch into two recursive calls, leading to exponential time.

💡 For strings of length 10, this can mean thousands of calls, which is impractical.

Interview Verdict: TLE / Use only to introduce problem structure

This approach is too slow for large inputs but essential to understand problem recursion.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while preserving the recursive intuition.

Intuition

Use the same recursion as brute force but store results of subproblems (i,j) in a cache to avoid repeated work.

Algorithm

1. Initialize a memo dictionary to store results for (i,j).
2. If (i,j) in memo, return stored result.
3. Apply same recursive logic as brute force.
4. Store result in memo before returning.

💡 Memoization turns exponential recursion into polynomial by remembering answers to subproblems.

Recurrence:Same as brute force: match(i,j) = (p[j] == s[i] or p[j] == '.') and match(i+1,j+1) or (p[j+1] == '*' and (match(i,j+2) or (first_match and match(i+1,j))))

</>

Code

def isMatch(s: str, p: str) -> bool:
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if j == len(p):
            ans = i == len(s)
        else:
            first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
            if j + 1 < len(p) and p[j+1] == '*':
                ans = dfs(i, j+2) or (first_match and dfs(i+1, j))
            else:
                ans = first_match and dfs(i+1, j+1)
        memo[(i, j)] = ans
        return ans
    return dfs(0, 0)

if __name__ == '__main__':
    print(isMatch('aab', 'c*a*b'))  # True

Line Notes

memo = {}Cache to store results of subproblems

if (i, j) in memo:Return cached result if available

if j == len(p):Base case: pattern exhausted

memo[(i, j)] = ansStore computed result before returning

return dfs(0, 0)Start matching from beginning of s and p

import java.util.*;
public class Solution {
    private Map<String, Boolean> memo = new HashMap<>();
    public boolean isMatch(String s, String p) {
        return dfs(s, p, 0, 0);
    }
    private boolean dfs(String s, String p, int i, int j) {
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        boolean ans;
        if (j == p.length()) {
            ans = i == s.length();
        } else {
            boolean firstMatch = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                ans = dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));
            } else {
                ans = firstMatch && dfs(s, p, i + 1, j + 1);
            }
        }
        memo.put(key, ans);
        return ans;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("aab", "c*a*b")); // true
    }
}

Line Notes

private Map<String, Boolean> memo = new HashMap<>();Cache for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if present

if (j == p.length())Base case: pattern exhausted

memo.put(key, ans);Store result before returning

return dfs(s, p, 0, 0);Start recursion from beginning

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
    unordered_map<string, bool> memo;
public:
    bool dfs(const string& s, const string& p, int i, int j) {
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        bool ans;
        if (j == p.size()) ans = (i == s.size());
        else {
            bool firstMatch = i < s.size() && (p[j] == s[i] || p[j] == '.');
            if (j + 1 < p.size() && p[j + 1] == '*') {
                ans = dfs(s, p, i, j + 2) || (firstMatch && dfs(s, p, i + 1, j));
            } else {
                ans = firstMatch && dfs(s, p, i + 1, j + 1);
            }
        }
        memo[key] = ans;
        return ans;
    }
    bool isMatch(string s, string p) {
        return dfs(s, p, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("aab", "c*a*b") << endl; // true
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache for memoization

if (memo.count(key)) return memo[key];Return cached result if available

if (j == p.size()) ans = (i == s.size());Base case: pattern exhausted

memo[key] = ans;Store result before returning

return dfs(s, p, 0, 0);Start recursion from beginning

function isMatch(s, p) {
    const memo = new Map();
    function dfs(i, j) {
        const key = i + ',' + j;
        if (memo.has(key)) return memo.get(key);
        let ans;
        if (j === p.length) {
            ans = i === s.length;
        } else {
            const firstMatch = i < s.length && (p[j] === s[i] || p[j] === '.');
            if (j + 1 < p.length && p[j + 1] === '*') {
                ans = dfs(i, j + 2) || (firstMatch && dfs(i + 1, j));
            } else {
                ans = firstMatch && dfs(i + 1, j + 1);
            }
        }
        memo.set(key, ans);
        return ans;
    }
    return dfs(0, 0);
}

console.log(isMatch('aab', 'c*a*b')); // true

Line Notes

const memo = new Map();Cache for memoization

if (memo.has(key)) return memo.get(key);Return cached result if present

if (j === p.length)Base case: pattern exhausted

memo.set(key, ans);Store result before returning

return dfs(0, 0);Start recursion from beginning

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) due to memo and recursion stack

Each subproblem (i,j) is computed once and stored, reducing exponential to polynomial time.

💡 For strings of length 1000, this means up to 1 million subproblems, which is feasible.

Interview Verdict: Accepted / Efficient for interview coding

Memoization is a practical optimization that balances clarity and performance.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from smaller subproblems, avoiding recursion and making the flow explicit and often easier to debug.

Intuition

Create a 2D dp table where dp[i][j] indicates if s[:i] matches p[:j]. Fill the table row by row using the recurrence relation.

Algorithm

1. Initialize dp array of size (len(s)+1) x (len(p)+1) with False.
2. Set dp[0][0] = True since empty string matches empty pattern.
3. Fill first row dp[0][j] for patterns that can match empty string (like a*, a*b*).
4. Iterate over i and j, fill dp[i][j] based on character matches and '*' handling.

💡 The table explicitly shows how matches build from empty prefixes to full strings.

Recurrence:dp[i][j] = (p[j-1] == s[i-1] or p[j-1] == '.') and dp[i-1][j-1] or (p[j-1] == '*' and (dp[i][j-2] or ((p[j-2] == s[i-1] or p[j-2] == '.') and dp[i-1][j])))

</>

Code

def isMatch(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]

if __name__ == '__main__':
    print(isMatch('aab', 'c*a*b'))  # True

Line Notes

dp = [[False] * (n + 1) for _ in range(m + 1)]Create DP table for all prefixes

dp[0][0] = TrueEmpty string matches empty pattern

if p[j - 1] == '*': dp[0][j] = dp[0][j - 2]Patterns like a* can match empty string

if p[j - 1] == '.' or p[j - 1] == s[i - 1]Current chars match or '.' wildcard

dp[i][j] = dp[i - 1][j - 1]Match depends on previous substrings

elif p[j - 1] == '*':Handle '*' by ignoring or matching one more char

dp[i][j] = dp[i][j - 2]Ignore '*' and preceding char

if p[j - 2] == '.' or p[j - 2] == s[i - 1]: dp[i][j] = dp[i][j] or dp[i - 1][j]Use '*' to match current char

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("aab", "c*a*b")); // true
    }
}

Line Notes

boolean[][] dp = new boolean[m + 1][n + 1];DP table for all prefixes

dp[0][0] = true;Empty string matches empty pattern

if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];Patterns like a* can match empty string

if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))Current chars match or '.' wildcard

dp[i][j] = dp[i - 1][j - 1];Match depends on previous substrings

else if (p.charAt(j - 1) == '*')Handle '*' by ignoring or matching one more char

dp[i][j] = dp[i][j - 2];Ignore '*' and preceding char

if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) dp[i][j] = dp[i][j] || dp[i - 1][j];Use '*' to match current char

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 2; j <= n; j++) {
            if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("aab", "c*a*b") << endl; // true
    return 0;
}

Line Notes

vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));DP table for all prefixes

dp[0][0] = true;Empty string matches empty pattern

if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];Patterns like a* can match empty string

if (p[j - 1] == '.' || p[j - 1] == s[i - 1])Current chars match or '.' wildcard

dp[i][j] = dp[i - 1][j - 1];Match depends on previous substrings

else if (p[j - 1] == '*')Handle '*' by ignoring or matching one more char

dp[i][j] = dp[i][j - 2];Ignore '*' and preceding char

if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) dp[i][j] = dp[i][j] || dp[i - 1][j];Use '*' to match current char

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 2; j <= n; j++) {
        if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2];
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    return dp[m][n];
}

console.log(isMatch('aab', 'c*a*b')); // true

Line Notes

const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));DP table for all prefixes

dp[0][0] = true;Empty string matches empty pattern

if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];Patterns like a* can match empty string

if (p[j - 1] === '.' || p[j - 1] === s[i - 1])Current chars match or '.' wildcard

dp[i][j] = dp[i - 1][j - 1];Match depends on previous substrings

else if (p[j - 1] === '*')Handle '*' by ignoring or matching one more char

dp[i][j] = dp[i][j - 2];Ignore '*' and preceding char

if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) dp[i][j] = dp[i][j] || dp[i - 1][j];Use '*' to match current char

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size (m+1)*(n+1), each cell computed in O(1).

💡 For strings of length 1000, this means about 1 million operations, which is efficient.

Interview Verdict: Accepted / Preferred in interviews for clarity and efficiency

Tabulation is often preferred because it avoids recursion and clearly shows the DP structure.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][*] and dp[i][*], we can optimize space by using two 1D arrays or even one with careful iteration.

Intuition

Use a 1D dp array representing the previous row and update it for the current row, iterating backwards over pattern indices to avoid overwriting needed values.

Algorithm

1. Initialize a 1D dp array of size n+1 with False, dp[0] = True.
2. Pre-fill dp for empty string matching patterns with '*'.
3. Iterate over string characters, updating dp backwards over pattern indices.
4. Use previous dp values and current character matches to update dp.
5. Return dp[n] as final answer.

💡 Backward iteration preserves previous state needed for '*' handling.

Recurrence:dp[j] = dp[j] or dp[j-2] if p[j-1] == '*', else dp[j] = dp[j-1] if chars match

</>

Code

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

if __name__ == '__main__':
    print(isMatch('aab', 'c*a*b'))  # True

Line Notes

dp = [False] * (n + 1)1D DP array for pattern prefixes

dp[0] = TrueEmpty string matches empty pattern

if p[j - 1] == '*': dp[j] = dp[j - 2]Patterns like a* can match empty string

prev = dp[0]Store previous dp[j-1] value for current iteration

dp[j] = dp[j] or dp[j - 2]Ignore '*' and preceding char

if p[j - 2] == '.' or p[j - 2] == s[i - 1]: dp[j] = dp[j] or prevUse '*' to match current char

dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])Match current chars without '*'

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') dp[j] = dp[j - 2];
        }
        for (int i = 1; i <= m; i++) {
            boolean prev = dp[0];
            dp[0] = false;
            for (int j = 1; j <= n; j++) {
                boolean temp = dp[j];
                if (p.charAt(j - 1) == '*') {
                    dp[j] = dp[j] || dp[j - 2];
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[j] = dp[j] || prev;
                    }
                } else {
                    dp[j] = prev && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1));
                }
                prev = temp;
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("aab", "c*a*b")); // true
    }
}

Line Notes

boolean[] dp = new boolean[n + 1];1D DP array for pattern prefixes

dp[0] = true;Empty string matches empty pattern

if (p.charAt(j - 1) == '*') dp[j] = dp[j - 2];Patterns like a* can match empty string

boolean prev = dp[0];Store previous dp[j-1] value for current iteration

dp[j] = dp[j] || dp[j - 2];Ignore '*' and preceding char

if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) dp[j] = dp[j] || prev;Use '*' to match current char

dp[j] = prev && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1));Match current chars without '*'

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int j = 2; j <= n; j++) {
            if (p[j - 1] == '*') dp[j] = dp[j - 2];
        }
        for (int i = 1; i <= m; i++) {
            bool prev = dp[0];
            dp[0] = false;
            for (int j = 1; j <= n; j++) {
                bool temp = dp[j];
                if (p[j - 1] == '*') {
                    dp[j] = dp[j] || dp[j - 2];
                    if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
                        dp[j] = dp[j] || prev;
                    }
                } else {
                    dp[j] = prev && (p[j - 1] == '.' || p[j - 1] == s[i - 1]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("aab", "c*a*b") << endl; // true
    return 0;
}

Line Notes

vector<bool> dp(n + 1, false);1D DP array for pattern prefixes

dp[0] = true;Empty string matches empty pattern

if (p[j - 1] == '*') dp[j] = dp[j - 2];Patterns like a* can match empty string

bool prev = dp[0];Store previous dp[j-1] value for current iteration

dp[j] = dp[j] || dp[j - 2];Ignore '*' and preceding char

if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) dp[j] = dp[j] || prev;Use '*' to match current char

dp[j] = prev && (p[j - 1] == '.' || p[j - 1] == s[i - 1]);Match current chars without '*'

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let j = 2; j <= n; j++) {
        if (p[j - 1] === '*') dp[j] = dp[j - 2];
    }
    for (let i = 1; i <= m; i++) {
        let prev = dp[0];
        dp[0] = false;
        for (let j = 1; j <= n; j++) {
            let temp = dp[j];
            if (p[j - 1] === '*') {
                dp[j] = dp[j] || dp[j - 2];
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[j] = dp[j] || prev;
                }
            } else {
                dp[j] = prev && (p[j - 1] === '.' || p[j - 1] === s[i - 1]);
            }
            prev = temp;
        }
    }
    return dp[n];
}

console.log(isMatch('aab', 'c*a*b')); // true

Line Notes

const dp = new Array(n + 1).fill(false);1D DP array for pattern prefixes

dp[0] = true;Empty string matches empty pattern

if (p[j - 1] === '*') dp[j] = dp[j - 2];Patterns like a* can match empty string

let prev = dp[0];Store previous dp[j-1] value for current iteration

dp[j] = dp[j] || dp[j - 2];Ignore '*' and preceding char

if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) dp[j] = dp[j] || prev;Use '*' to match current char

dp[j] = prev && (p[j - 1] === '.' || p[j - 1] === s[i - 1]);Match current chars without '*'

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single dp array of size n+1 and update it for each character in s.

💡 This reduces memory usage significantly while maintaining the same time complexity.

Interview Verdict: Accepted / Best for memory constrained environments

Space optimization is a valuable skill to demonstrate after mastering full DP.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are best for interviews; brute force is for understanding; space optimization is optional but impressive.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n)	Possible but unlikely for constraints	Yes	Code if comfortable with recursion
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Preferred for clarity and control
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	Harder	Mention or code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show problem structure.Introduce memoization to optimize recursion.Present bottom-up DP for iterative clarity.Discuss space optimization if time permits.

Time Allocation

Clarify: 2min → Brute Force: 5min → Memoization: 5min → Tabulation: 7min → Space Optimization: 3min → Testing: 3min. Total ~25min

What the Interviewer Tests

Understanding of recursion and DP, ability to handle complex pattern matching, and optimization skills.

Common Follow-ups

• How to handle '+' quantifier (one or more)? → Modify DP to require at least one match before '*' logic.
• Can you extend to support '?' (zero or one)? → Add cases to handle optional preceding char.

💡 These follow-ups test your ability to adapt the DP framework to more complex regex features.

🔍

Pattern Recognition

When to Use

1) Problem involves matching strings with '.' and '*' wildcards; 2) Need full string match; 3) Overlapping subproblems with recursive structure; 4) DP table or memoization fits naturally.

Signature Phrases

'.' matches any single character'*' matches zero or more of the preceding element

NOT This Pattern When

Problems with simple substring search or exact matching without wildcards

Similar Problems

Wildcard Matching - similar but with '?' and '*' as wildcardsEdit Distance - string transformation with DPLongest Common Subsequence - foundational string DP problem

Practice

1. Consider the following Python code implementing wildcard matching using space-optimized DP. What is the value of prev[3] after processing i=2 (second character of s='abc') and j=3 (third character of p='a*c')?

easy

A. True

B. Raises an IndexError

C. Depends on previous iteration, cannot determine

D. False

Solution

1. Step 1: Trace dp arrays for i=2, j=3

   At i=2 (s[1]='b'), j=3 (p[2]='c'), since p[j-1] != '*' and not '?', check if s[i-1]==p[j-1]. 'b' != 'c', so curr[3] = False from prev[2].

2. Step 2: Evaluate curr[3]

   At j=2, p[1]='*', so curr[2] can be True if curr[1] or prev[2] is True. However, curr[3] depends on prev[2], which is False at this point, so curr[3] remains False.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP correctly updates curr[3] to False at i=2, j=3 [OK]

Hint: Check character matches and '*' propagation carefully [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing curr and prev arrays
• Ignoring '*' propagation

2. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Longest Common Subsequence problem, where the input strings have lengths m and n respectively?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify time complexity

   The algorithm uses two nested loops: outer loop runs m times, inner loop runs n times, resulting in O(m*n) time.

2. Step 2: Identify space complexity

   Space optimized DP uses a single array of size n+1, so space complexity is O(n). The recursion stack or full DP table is not used.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops give O(m*n) time; single dp array gives O(n) space [OK]

Hint: Nested loops multiply time; single dp array reduces space [OK]

Common Mistakes:

• Confusing full DP table space with optimized space
• Assuming linear time due to single dp array
• Forgetting recursion stack space in brute force

3. The following code attempts to implement the space-optimized LCS algorithm. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: for j in range(1, n + 1): # iterating forwards

B. Line 5: for i in range(1, m + 1):

C. Line 9: if text1[i - 1] == text2[j - 1]:

D. Line 12: prev = temp

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards (j=1 to n), which causes dp[j-1] to be overwritten before it is used in the max calculation.

2. Step 2: Understand impact of forward iteration

   Because dp[j-1] is updated before dp[j], the algorithm uses updated values instead of previous iteration's values, leading to incorrect LCS length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inner loop must iterate backwards to preserve dp[j-1] values [OK]

Hint: Inner loop must run backwards to avoid overwriting dp array [OK]

Common Mistakes:

• Iterating inner loop forwards in space optimized DP
• Mixing up indices in character comparison
• Incorrect initialization of prev variable

4. The following code attempts to find the longest palindromic substring using DP. Identify the line containing the subtle bug that causes incorrect results for some inputs.

medium

A. Line: if length < 3:

B. Line: dp[i][i] = True

C. Line: dp[i][j] = dp[i + 1][j - 1]

D. Line: for i in range(n - length + 1):

Solution

1. Step 1: Compare condition with correct code

   The correct condition is length <= 3, but here it is length < 3, so length=3 substrings are not handled correctly.

2. Step 2: Understand impact

   For length=3, dp[i][j] should be True if s[i]==s[j], but this code skips that, causing missed palindromes of length 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing < to <= fixes the bug [OK]

Hint: Check boundary conditions for length 3 palindromes [OK]

Common Mistakes:

• Off-by-one in length condition
• Confusing substring indices
• Incorrect DP table initialization

5. Suppose you want to find the longest palindromic subsequence in a string where characters can be reused unlimited times. Which modification to the DP approach correctly handles this variant?

hard

A. Modify DP to consider infinite reuse by allowing i to stay fixed while j moves, and vice versa

B. Use a greedy approach selecting matching characters repeatedly from both ends

C. Use the same DP but allow indices i and j to move independently without restriction

D. This problem reduces to longest palindromic substring, so use Manacher's algorithm

Solution

1. Step 1: Understand reuse means characters can be counted multiple times

   Standard LPS counts each character once; reuse requires relaxing index movement constraints.

2. Step 2: Modify DP transitions to allow staying at i or j to reuse characters

   DP must consider cases where i or j does not advance to reuse characters, effectively allowing repeated use.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing indices to stay or move independently models reuse correctly [OK]

Hint: Reuse means relaxing index movement in DP transitions [OK]

Common Mistakes:

• Using greedy approach
• Confusing substring with subsequence
• Applying substring algorithms incorrectly