Definition
Regular Expression Matching uses 2D DP where dp[i][j] means the first i text chars match the first j pattern chars.
- Star case gives two options: zero occurrences via
dp[i][j-2], or one-more occurrence when the preceding pattern char matches the current text char viadp[i-1][j]. - Single match for a literal char or dot requires
dp[i-1][j-1]plus a character match. - First row handles patterns like
a*b*that can match empty text. - Time is O(m * n) and space is O(m * n), reducible to O(n).
- Full match is required: the pattern must cover the entire text, not just a substring.
A reference-format validator at National Bank of India checks whether an account reference matches a pattern with wildcards. A dot matches any one character, and a star means the element before it can repeat any number of times including zero. At a star the validator tries both using none and using one more.
Understanding the Concepts
What is the Regular Expression Matching Problem?
Implement pattern matching where . matches any single character and * matches zero or more of the preceding element. The match must cover the entire input string, not just a substring.
At National Bank of India, Rajesh validates account reference strings against patterns. The pattern a.b*c matches references like "axc", "axbc", "axbbc", etc.
package com.bank.service;
public class RegexMatching {
public static 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;
// First row: patterns like a*, a*b*, a*b*c* can match empty text
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++) {
char pc = p.charAt(j - 1);
if (pc == '*') {
// Zero occurrences: skip the x* pair
dp[i][j] = dp[i][j - 2];
// One more occurrence: preceding char matches current text char
char prev = p.charAt(j - 2);
if (prev == '.' || prev == s.charAt(i - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (pc == '.' || pc == s.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("aab", "c*a*b")); // true
System.out.println(isMatch("mississippi", "mis*is*p*.")); // false
System.out.println(isMatch("ab", ".*")); // true
}
}
true
false
true
Why Is the Star Case Difficult?
The star is the whole difficulty because it modifies the preceding element rather than standing alone. a* means zero or more as, not zero or more of anything. This means the star looks back two positions for the zero case and consumes one text character for the one-more case.
package com.bank.core;
public class StarCaseExplained {
// Pattern: "xa*b", Text: "xb"
// Star takes zero 'a's: skip 'a*' -> match "xb" against "xb" -> true
// Pattern: "xa*b", Text: "xaaab"
// Star takes three 'a's: consume 'a' three times -> match "xaaab" against "xa*b" -> true
// Two branches at star:
// 1. dp[i][j-2]: zero occurrences (skip the x* pair)
// 2. dp[i-1][j]: one more occurrence (preceding matches, consume one text char)
}
How Does the First Row Work?
The first row represents matching an empty text. A pattern like a* can match empty text because the star takes zero occurrences. A pattern like a*b*c* can also match empty text if each star takes zero. We set dp[0][j] = dp[0][j-2] when the pattern char at j is a star.
package com.bank.core;
public class FirstRowExplained {
public static void main(String[] args) {
String p = "a*b*c";
int n = p.length();
boolean[] firstRow = new boolean[n + 1];
firstRow[0] = true;
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
firstRow[j] = firstRow[j - 2];
}
}
// firstRow: [T, F, T, F, T, F]
// 0 a * b * c
// dp[0][2]=T: a* matches empty (zero a's)
// dp[0][4]=T: a*b* matches empty (zero a's, zero b's)
// dp[0][5]=F: a*b*c requires at least one c
for (int j = 0; j <= n; j++) {
System.out.println("dp[0][" + j + "] = " + firstRow[j]);
}
}
}
dp[0][0] = true
dp[0][1] = false
dp[0][2] = true
dp[0][3] = false
dp[0][4] = true
dp[0][5] = false
How Is This Different from Wildcard Matching?
| Aspect | Regex Matching (. and *) | Wildcard Matching (? and *) |
|---|---|---|
| Star meaning | Zero or more of PRECEDING element | Any sequence of characters (standalone) |
| Star dependency | Tied to previous char (x*) | Independent (matches anything) |
| Zero case | dp[i][j-2] (skip x* pair) | dp[i][j-1] (skip star) |
| One-more case | dp[i-1][j] if preceding matches | dp[i-1][j] (absorb one char) |
| Complexity | O(m*n) | O(m*n) |
// Regex *: dp[i][j] = dp[i][j-2] || (prevMatch && dp[i-1][j])
// Wildcard *: dp[i][j] = dp[i][j-1] || dp[i-1][j]
What Are Common Mistakes?
The first mistake is forgetting the zero-occurrences case for star. The second is not checking that the preceding pattern character matches the current text character before allowing one-more.
Wrong code:
// WRONG: only handles one-more case, misses zero occurrences
if (pc == '*') {
dp[i][j] = dp[i - 1][j]; // BUG: no zero-occurrences check
}
Correct code:
// CORRECT: both zero and one-more cases
if (pc == '*') {
dp[i][j] = dp[i][j - 2]; // zero occurrences
if (prev == '.' || prev == s.charAt(i - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j]; // one more
}
}
What About the Recursive Approach?
The recursive approach with memoization is often easier to write and understand. We match characters from left to right, handling the star by branching into zero and one-more.
package com.bank.core;
public class RegexRecursive {
private static Boolean[][] memo;
public static boolean isMatch(String s, String p) {
memo = new Boolean[s.length() + 1][p.length() + 1];
return dp(s, p, 0, 0);
}
private static boolean dp(String s, String p, int i, int j) {
if (j == p.length()) return i == s.length();
if (memo[i][j] != null) return memo[i][j];
boolean firstMatch = i < s.length()
&& (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
boolean result;
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
result = dp(s, p, i, j + 2) // zero occurrences
|| (firstMatch && dp(s, p, i + 1, j)); // one more
} else {
result = firstMatch && dp(s, p, i + 1, j + 1); // single match
}
memo[i][j] = result;
return result;
}
}
What About Space Optimization?
Since each row depends only on the previous row, we can reduce space from O(m*n) to O(n) using two rolling arrays.
package com.bank.core;
public class RegexSpaceOptimized {
// Use two 1D arrays: prev and curr
// After processing each text character, swap them
// Space: O(n) where n = pattern length
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Wildcard Matching: star is standalone, not tied to preceding element.
- What if star can appear alone (not after another char)? Invalid pattern in standard regex.
- Support
+(one or more): same as star but without the zero case. - Support
?(zero or one): replace dp[i-1][j] with dp[i-1][j-2] for the one case.
package com.bank.core;
public class RegexFollowUps {
// Wildcard: * is standalone, simpler star logic
// Plus (+): one or more = firstMatch && dp[i-1][j] (no zero case)
// Question mark (?): zero or one = dp[i][j-2] || (firstMatch && dp[i-1][j-2])
}
Visual Overview
DP Table for s="aab", p="c*a*b":
"" c * a * b
"" [ T F T F T F ]
a [ F F F T T F ]
a [ F F F F T F ]
b [ F F F F F T ]
Star at j=2 (c*): zero c's -> dp[0][2] = dp[0][0] = T
Star at j=4 (a*): zero a's -> dp[0][4] = dp[0][2] = T
Star Logic:
┌─────────────────────────────────────┐
│ When pattern[j] == '*': │
│ │
│ Option 1: Zero occurrences │
│ dp[i][j] = dp[i][j-2] │
│ (skip the x* pair entirely) │
│ │
│ Option 2: One more occurrence │
│ if prev matches text[i]: │
│ dp[i][j] |= dp[i-1][j] │
│ (consume one text char, stay at *) │
└─────────────────────────────────────┘
Key Takeaway
Regular Expression Matching with dot and star is a two-dimensional DP problem. I define dp[i][j] as whether the first i characters of the text match the first j characters of the pattern. The empty-empty cell is true, and I handle the first row specially so that patterns like a* or a*b* can match empty text by letting each star take zero occurrences.
The body has two cases. For a normal character or dot, the cell is true only if the diagonal is true and the single character matches. For a star, there are two possibilities combined with OR: zero occurrences of the preceding element (look back two pattern positions) or one more occurrence when the preceding element matches the current text character (consume one text char and stay on the same pattern position).
The star is the whole difficulty because it modifies the preceding element rather than standing alone, which distinguishes this from Wildcard Matching where star is independent. The two classic bugs are forgetting the zero-occurrences branch and not checking that the preceding pattern character matches before allowing one-more.
In my project at National Bank of India, a validator checked whether account reference strings matched patterns with dot and star wildcards. The DP correctly handled both zero and many repetitions, which a simple left-to-right scan cannot do because it cannot backtrack.
Remember one sentence: star gives two options at each cell: skip the x-star pair for zero occurrences, or consume one text char if the preceding element matches.
---