Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.'*' Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'.
Therefore, by repeating 'a' once, it becomes "aa".
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 2 times.
1 ≤ s.length ≤ 201 ≤ p.length ≤ 30s contains only lowercase English letters.p contains only lowercase English letters, '.', and '*'.'*', there will be a previous valid character to match.Complex DP problem with wildcard matching!
Two special cases to handle:
. matches any single character* matches zero or more of preceding elementBuild a table where dp[i][j] = true if s[0..i-1] matches p[0..j-1]
dp[m+1][n+1] tabledp[0][0] = true (empty matches empty)a*, a*b* matching empty stringp[j-1] is not *:
dp[i-1][j-1]p[j-1] is *:
dp[i][j-2]dp[i-1][j]dp[m][n]Top-down recursive approach with memoization.
isMatch(i, j): does s[i..] match p[j..]?* specially*: check first char match + recurse*: try zero or more matchesUse rolling array to reduce space.
| Approach | Time | Space | |----------|------|-------| | 2D DP | O(m × n) | O(m × n) | | Memoization | O(m × n) | O(m × n) | | Space Optimized | O(m × n) | O(n) |
This problem demonstrates:
1import java.util.*;
2
3class Solution {
4 // Solution 1: 2D Dynamic Programming
5 public boolean isMatch(String s, String p) {
6 int m = s.length();
7 int n = p.length();
8
9 // dp[i][j] = does s[0..i-1] match p[0..j-1]?
10 boolean[][] dp = new boolean[m + 1][n + 1];
11
12 // Base case: empty string matches empty pattern
13 dp[0][0] = true;
14
15 // Handle patterns like a*, a*b*, a*b*c* that can match empty string
16 for (int j = 2; j <= n; j++) {
17 if (p.charAt(j - 1) == '*') {
18 dp[0][j] = dp[0][j - 2];
19 }
20 }
21
22 // Fill the DP table
23 for (int i = 1; i <= m; i++) {
24 for (int j = 1; j <= n; j++) {
25 if (p.charAt(j - 1) == '*') {
26 // Star can match zero or more of preceding element
27 // Zero occurrences: look at dp[i][j-2]
28 dp[i][j] = dp[i][j - 2];
29
30 // One or more occurrences: check if chars match
31 char prevPatternChar = p.charAt(j - 2);
32 if (prevPatternChar == s.charAt(i - 1) || prevPatternChar == '.') {
33 dp[i][j] = dp[i][j] || dp[i - 1][j];
34 }
35 } else {
36 // Regular character or dot
37 if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
38 dp[i][j] = dp[i - 1][j - 1];
39 }
40 }
41 }
42 }
43
44 return dp[m][n];
45 }
46
47 // Solution 2: Recursion with Memoization
48 public boolean isMatchMemo(String s, String p) {
49 Map<String, Boolean> memo = new HashMap<>();
50 return dp(s, p, 0, 0, memo);
51 }
52
53 private boolean dp(String s, String p, int i, int j, Map<String, Boolean> memo) {
54 // Check memo
55 String key = i + "," + j;
56 if (memo.containsKey(key)) {
57 return memo.get(key);
58 }
59
60 // Base case: pattern exhausted
61 if (j == p.length()) {
62 return i == s.length();
63 }
64
65 // Check if first characters match
66 boolean firstMatch = i < s.length() &&
67 (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
68
69 boolean result;
70
71 // Handle star
72 if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
73 // Two options:
74 // 1. Zero occurrences: skip pattern[j] and '*'
75 // 2. One+ occurrences: match first char and keep '*'
76 result = dp(s, p, i, j + 2, memo) || // zero occurrences
77 (firstMatch && dp(s, p, i + 1, j, memo)); // one+ occurrences
78 } else {
79 // No star: must match first char and continue
80 result = firstMatch && dp(s, p, i + 1, j + 1, memo);
81 }
82
83 memo.put(key, result);
84 return result;
85 }
86
87 // Solution 3: Space Optimized DP
88 public boolean isMatchOptimized(String s, String p) {
89 int m = s.length();
90 int n = p.length();
91
92 // Use two 1D arrays
93 boolean[] prev = new boolean[n + 1];
94 boolean[] curr = new boolean[n + 1];
95
96 // Base case
97 prev[0] = true;
98
99 // Handle patterns that can match empty string
100 for (int j = 2; j <= n; j++) {
101 if (p.charAt(j - 1) == '*') {
102 prev[j] = prev[j - 2];
103 }
104 }
105
106 // Fill row by row
107 for (int i = 1; i <= m; i++) {
108 curr[0] = false; // Empty pattern can't match non-empty string
109
110 for (int j = 1; j <= n; j++) {
111 if (p.charAt(j - 1) == '*') {
112 // Zero occurrences
113 curr[j] = curr[j - 2];
114
115 // One or more occurrences
116 char prevPatternChar = p.charAt(j - 2);
117 if (prevPatternChar == s.charAt(i - 1) || prevPatternChar == '.') {
118 curr[j] = curr[j] || prev[j];
119 }
120 } else {
121 // Regular character or dot
122 if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
123 curr[j] = prev[j - 1];
124 } else {
125 curr[j] = false;
126 }
127 }
128 }
129
130 // Swap arrays
131 boolean[] temp = prev;
132 prev = curr;
133 curr = temp;
134 Arrays.fill(curr, false);
135 }
136
137 return prev[n];
138 }
139
140 // Solution 4: Clean Recursive
141 public boolean isMatchRecursive(String s, String p) {
142 // Base case: pattern exhausted
143 if (p.isEmpty()) {
144 return s.isEmpty();
145 }
146
147 // Check if first characters match
148 boolean firstMatch = !s.isEmpty() &&
149 (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
150
151 // Handle star
152 if (p.length() >= 2 && p.charAt(1) == '*') {
153 // Two options:
154 // 1. Zero occurrences: skip current pattern char and '*'
155 // 2. One+ occurrences: match first char and keep pattern
156 return isMatchRecursive(s, p.substring(2)) ||
157 (firstMatch && isMatchRecursive(s.substring(1), p));
158 } else {
159 // No star: must match first char and continue
160 return firstMatch && isMatchRecursive(s.substring(1), p.substring(1));
161 }
162 }
163}
164