Beim klassischen algorithmischen Regular Expression Matching enthält das Pattern normale Zeichen sowie:
. → genau ein beliebiges Zeichen
* → null oder mehr Wiederholungen des vorherigen Elements
Beispiel:
aa
gegen
a*
liefert true.
Dot
. repräsentiert genau ein Zeichen.
c.t
passt beispielsweise zu cat, cut oder c9t.
Star
* gehört zum vorherigen Pattern-Element.
a*
kann leer sein oder beliebig viele a enthalten.
Dynamic Programming
Wir definieren:
dp[i][j]
als die Information, ob die ersten i Zeichen des Strings vollständig zu den ersten j Zeichen des Patterns passen.
dp[0][0] = true
Patterns wie a*b*c* können auch einen leeren String matchen.
Normale Zeichen
Sind Zeichen gleich oder das Pattern enthält ., gilt:
dp[i][j] = dp[i - 1][j - 1]
Star
Zuerst kann x* vollständig ausgelassen werden:
dp[i][j] = dp[i][j - 2]
Passt x zum aktuellen Stringzeichen, kann * noch ein Zeichen konsumieren:
dp[i][j] = dp[i][j] || dp[i - 1][j]
TypeScript
function isRegexMatch(s: string, p: string): boolean {
const dp = Array.from(
{ length: s.length + 1 },
() => new Array(p.length + 1).fill(false)
);
dp[0][0] = true;
for (let j = 2; j <= p.length; j++) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (let i = 1; i <= s.length; i++) {
for (let j = 1; j <= p.length; 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[s.length][p.length];
}
Komplexität
Time: O(n × m)
Space: O(n × m)
Rekursion und Memoization
Die Aufgabe kann auch rekursiv formuliert werden.
Bei x* gibt es zwei Möglichkeiten:
x* überspringen
oder bei passendem Zeichen:
ein Zeichen konsumieren und x* behalten
Ohne Memoization werden dieselben Teilprobleme mehrfach berechnet.
Regex vs. Wildcard
Beim Regex bedeutet * Wiederholung des vorherigen Elements.
Beim typischen Wildcard Matching bedeutet * dagegen eine beliebige Zeichenfolge.
Dieser Unterschied ist entscheidend.
Full Match
Die Aufgabe fordert eine vollständige Übereinstimmung.
ell matcht daher nicht den gesamten String hello.
Anwendungen
Reguläre Ausdrücke werden in realen Systemen für Validation, Suche, Log-Filterung und Textverarbeitung verwendet.
Für Produktivcode sollten jedoch die ausgereiften Regex Engines der jeweiligen Plattform verwendet werden.
Interviewwissen
Wichtig sind insbesondere:
- Bedeutung von
.. - Bedeutung von
*. - DP-State.
- Empty-String-Initialisierung.
- Zero-vs.-multiple-occurrence-Logik.
O(n × m)Komplexität.
Fazit
Regular Expression Matching ist ein klassisches Beispiel dafür, rekursive Verzweigungen mit Dynamic Programming effizient zu modellieren.