Skip to content

10. Regular Expression Matching

Description

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.

Return a boolean indicating whether the matching covers the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

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".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

 

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Solutions

Thinking

Matching left to right and, at each *, trying \(0,1,2,\ldots\) repetitions is the natural search. \(s\) and \(p\) are at most length \(20\), so exponential time sometimes passes, but the same pair of positions is recomputed over and over.

A * applies only to the preceding token: either match it \(0\) times (skip two pattern indices), or the current character fits that token (including .) and the same * consumes the next character of \(s\). A plain character must be consumed one-for-one.

The state is therefore “can suffix \(i\) of \(s\) match suffix \(j\) of \(p\)”. Search with memoization so exponential branches collapse to \(O(mn)\) pairs \((i,j)\).

We design a function \(dfs(i, j)\), which indicates whether the \(i\)-th character of \(s\) matches the \(j\)-th character of \(p\). The answer is \(dfs(0, 0)\).

The calculation process of the function \(dfs(i, j)\) is as follows:

  • If \(j\) has reached the end of \(p\), then if \(i\) has also reached the end of \(s\), the match is successful, otherwise, the match fails.
  • If the next character of \(j\) is '*', we can choose to match \(0\) \(s[i]\) characters, which is \(dfs(i, j + 2)\). If \(i \lt m\) and \(s[i]\) matches \(p[j]\), we can choose to match \(1\) \(s[i]\) character, which is \(dfs(i + 1, j)\).
  • If the next character of \(j\) is not '*', then if \(i \lt m\) and \(s[i]\) matches \(p[j]\), it is \(dfs(i + 1, j + 1)\). Otherwise, the match fails.

During the process, we can use memoization search to avoid repeated calculations.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the lengths of \(s\) and \(p\) respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i, j):
            if j >= n:
                return i == m
            if j + 1 < n and p[j + 1] == '*':
                return dfs(i, j + 2) or (
                    i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j)
                )
            return i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j + 1)

        m, n = len(s), len(p)
        return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private Boolean[][] f;
    private String s;
    private String p;
    private int m;
    private int n;

    public boolean isMatch(String s, String p) {
        m = s.length();
        n = p.length();
        f = new Boolean[m + 1][n + 1];
        this.s = s;
        this.p = p;
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (j >= n) {
            return i == m;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        boolean res = false;
        if (j + 1 < n && p.charAt(j + 1) == '*') {
            res = dfs(i, j + 2)
                || (i < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && dfs(i + 1, j));
        } else {
            res = i < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && dfs(i + 1, j + 1);
        }
        return f[i][j] = res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof f);
        function<bool(int, int)> dfs = [&](int i, int j) -> bool {
            if (j >= n) {
                return i == m;
            }
            if (f[i][j]) {
                return f[i][j] == 1;
            }
            int res = -1;
            if (j + 1 < n && p[j + 1] == '*') {
                if (dfs(i, j + 2) or (i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j))) {
                    res = 1;
                }
            } else if (i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j + 1)) {
                res = 1;
            }
            f[i][j] = res;
            return res == 1;
        };
        return dfs(0, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    var dfs func(i, j int) bool
    dfs = func(i, j int) bool {
        if j >= n {
            return i == m
        }
        if f[i][j] != 0 {
            return f[i][j] == 1
        }
        res := -1
        if j+1 < n && p[j+1] == '*' {
            if dfs(i, j+2) || (i < m && (s[i] == p[j] || p[j] == '.') && dfs(i+1, j)) {
                res = 1
            }
        } else if i < m && (s[i] == p[j] || p[j] == '.') && dfs(i+1, j+1) {
            res = 1
        }
        f[i][j] = res
        return res == 1
    }
    return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let (m, n) = (s.len(), p.len());
        let mut f = vec![vec![0; n + 1]; m + 1];

        fn dfs(
            s: &Vec<char>,
            p: &Vec<char>,
            f: &mut Vec<Vec<i32>>,
            i: usize,
            j: usize,
            m: usize,
            n: usize,
        ) -> bool {
            if j >= n {
                return i == m;
            }
            if f[i][j] != 0 {
                return f[i][j] == 1;
            }
            let mut res = -1;
            if j + 1 < n && p[j + 1] == '*' {
                if dfs(s, p, f, i, j + 2, m, n)
                    || (i < m && (s[i] == p[j] || p[j] == '.') && dfs(s, p, f, i + 1, j, m, n))
                {
                    res = 1;
                }
            } else if i < m && (s[i] == p[j] || p[j] == '.') && dfs(s, p, f, i + 1, j + 1, m, n) {
                res = 1;
            }
            f[i][j] = res;
            res == 1
        }

        dfs(
            &s.chars().collect(),
            &p.chars().collect(),
            &mut f,
            0,
            0,
            m,
            n,
        )
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    const dfs = (i, j) => {
        if (j >= n) {
            return i === m;
        }
        if (f[i][j]) {
            return f[i][j] === 1;
        }
        let res = -1;
        if (j + 1 < n && p[j + 1] === '*') {
            if (dfs(i, j + 2) || (i < m && (s[i] === p[j] || p[j] === '.') && dfs(i + 1, j))) {
                res = 1;
            }
        } else if (i < m && (s[i] === p[j] || p[j] === '.') && dfs(i + 1, j + 1)) {
            res = 1;
        }
        f[i][j] = res;
        return res === 1;
    };
    return dfs(0, 0);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    private string s;
    private string p;
    private int m;
    private int n;
    private int[,] f;

    public bool IsMatch(string s, string p) {
        m = s.Length;
        n = p.Length;
        f = new int[m + 1, n + 1];
        this.s = s;
        this.p = p;
        return dfs(0, 0);
    }

    private bool dfs(int i, int j) {
        if (j >= n) {
            return i == m;
        }
        if (f[i, j] != 0) {
            return f[i, j] == 1;
        }
        int res = -1;
        if (j + 1 < n && p[j + 1] == '*') {
            if (dfs(i, j + 2) || (i < m && (s[i] == p[j] || p[j] == '.') && dfs(i + 1, j))) {
                res = 1;
            }
        } else if (i < m && (s[i] == p[j] || p[j] == '.') && dfs(i + 1, j + 1)) {
            res = 1;
        }
        f[i, j] = res;
        return res == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MAX_LEN 1000

char *ss, *pp;
int m, n;
int f[MAX_LEN + 1][MAX_LEN + 1];

bool dfs(int i, int j) {
    if (j >= n) {
        return i == m;
    }
    if (f[i][j] != 0) {
        return f[i][j] == 1;
    }
    int res = -1;
    if (j + 1 < n && pp[j + 1] == '*') {
        if (dfs(i, j + 2) || (i < m && (ss[i] == pp[j] || pp[j] == '.') && dfs(i + 1, j))) {
            res = 1;
        }
    } else if (i < m && (ss[i] == pp[j] || pp[j] == '.') && dfs(i + 1, j + 1)) {
        res = 1;
    }
    f[i][j] = res;
    return res == 1;
}

bool isMatch(char* s, char* p) {
    ss = s;
    pp = p;
    m = strlen(s);
    n = strlen(p);
    memset(f, 0, sizeof(f));
    return dfs(0, 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $f = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

        $dfs = function ($i, $j) use (&$s, &$p, $m, $n, &$f, &$dfs) {
            if ($j >= $n) {
                return $i == $m;
            }
            if ($f[$i][$j] != 0) {
                return $f[$i][$j] == 1;
            }
            $res = -1;
            if ($j + 1 < $n && $p[$j + 1] == '*') {
                if (
                    $dfs($i, $j + 2) ||
                    ($i < $m && ($s[$i] == $p[$j] || $p[$j] == '.') && $dfs($i + 1, $j))
                ) {
                    $res = 1;
                }
            } elseif ($i < $m && ($s[$i] == $p[$j] || $p[$j] == '.') && $dfs($i + 1, $j + 1)) {
                $res = 1;
            }
            $f[$i][$j] = $res;
            return $res == 1;
        };

        return $dfs(0, 0);
    }
}

Solution 2: Dynamic Programming

Thinking

Memoized Solution 1 is already \(O(mn)\), but it is still recursion: implicit stack depth and larger constants. The transitions have no aftereffect, so we can fill \(i,j\) in increasing order.

\(f[i][j]\) is whether the first \(i\) characters of \(s\) match the first \(j\) of \(p\). Empty matches empty. We also need \(i=0\) so patterns like a* can match the empty string, which is why the outer loop starts from the empty prefix.

The * cases are the same as Solution 1: skip two pattern characters, or consume one more character of \(s\) when it fits. After filling the table we read \(f[m][n]\).

We can convert the memoization search in Solution 1 into dynamic programming.

Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). The answer is \(f[m][n]\). Initialize \(f[0][0] = true\), indicating that the empty string and the empty regular expression match.

Similar to Solution 1, we can discuss different cases.

  • If \(p[j - 1]\) is '*', we can choose to match \(0\) \(s[i - 1]\) characters, which is \(f[i][j] = f[i][j - 2]\). If \(s[i - 1]\) matches \(p[j - 2]\), we can choose to match \(1\) \(s[i - 1]\) character, which is \(f[i][j] = f[i][j] \lor f[i - 1][j]\).
  • If \(p[j - 1]\) is not '*', then if \(s[i - 1]\) matches \(p[j - 1]\), it is \(f[i][j] = f[i - 1][j - 1]\). Otherwise, the match fails.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the lengths of \(s\) and \(p\) respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i][j - 2]
                    if i > 0 and (p[j - 2] == "." or s[i - 1] == p[j - 2]):
                        f[i][j] |= f[i - 1][j]
                elif i > 0 and (p[j - 1] == "." or s[i - 1] == p[j - 1]):
                    f[i][j] = f[i - 1][j - 1]
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (i > 0 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
                        f[i][j] |= f[i - 1][j];
                    }
                } else if (i > 0
                    && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[m][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        bool f[m + 1][n + 1];
        memset(f, false, sizeof f);
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 2];
                    if (i && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
                        f[i][j] |= f[i - 1][j];
                    }
                } else if (i && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m+1)
    for i := range f {
        f[i] = make([]bool, n+1)
    }
    f[0][0] = true
    for i := 0; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i][j-2]
                if i > 0 && (p[j-2] == '.' || p[j-2] == s[i-1]) {
                    f[i][j] = f[i][j] || f[i-1][j]
                }
            } else if i > 0 && (p[j-1] == '.' || p[j-1] == s[i-1]) {
                f[i][j] = f[i-1][j-1]
            }
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let m = s.len();
        let n = p.len();
        let mut f = vec![vec![false; n + 1]; m + 1];

        f[0][0] = true;

        let s: Vec<char> = s.chars().collect();
        let p: Vec<char> = p.chars().collect();

        for i in 0..=m {
            for j in 1..=n {
                if p[j - 1] == '*' {
                    f[i][j] = f[i][j - 2];
                    if i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else if i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }

        f[m][n]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    f[0][0] = true;
    for (let i = 0; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i][j - 2];
                if (i && (p[j - 2] === '.' || p[j - 2] === s[i - 1])) {
                    f[i][j] |= f[i - 1][j];
                }
            } else if (i && (p[j - 1] === '.' || p[j - 1] === s[i - 1])) {
                f[i][j] = f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] f = new bool[m + 1, n + 1];
        f[0, 0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i, j] = f[i, j - 2];
                    if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
                        f[i, j] |= f[i - 1, j];
                    }
                } else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
                    f[i, j] = f[i - 1, j - 1];
                }
            }
        }
        return f[m, n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);

        $f = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
        $f[0][0] = true;

        for ($i = 0; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($p[$j - 1] == '*') {
                    $f[$i][$j] = $f[$i][$j - 2];
                    if ($i > 0 && ($p[$j - 2] == '.' || $p[$j - 2] == $s[$i - 1])) {
                        $f[$i][$j] = $f[$i][$j] || $f[$i - 1][$j];
                    }
                } elseif ($i > 0 && ($p[$j - 1] == '.' || $p[$j - 1] == $s[$i - 1])) {
                    $f[$i][$j] = $f[$i - 1][$j - 1];
                }
            }
        }

        return $f[$m][$n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
bool isMatch(char* s, char* p) {
    int m = strlen(s), n = strlen(p);
    bool f[m + 1][n + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = true;

    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[i][j] = f[i][j - 2];
                if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
                    f[i][j] = f[i][j] || f[i - 1][j];
                }
            } else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
                f[i][j] = f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
}

Comments