Skip to content

Files

Latest commit

klever34klever34
feat: add swift implementation to lcof problem: No.19 (#2878)
May 22, 2024
c79c5e2 · May 22, 2024

History

History

面试题19. 正则表达式匹配

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
May 22, 2024
Solution.cpp
Solution.cpp
Jan 13, 2024
Solution.cs
Solution.cs
Jan 13, 2024
Solution.go
Solution.go
Jan 13, 2024
Solution.java
Solution.java
Jan 13, 2024
Solution.js
Solution.js
Jan 13, 2024
Solution.py
Solution.py
Jan 13, 2024
Solution.swift
Solution.swift
May 22, 2024
Solution2.cpp
Solution2.cpp
Jan 13, 2024
Solution2.cs
Solution2.cs
Jan 13, 2024
Solution2.go
Solution2.go
Jan 13, 2024
Solution2.java
Solution2.java
Jan 13, 2024
Solution2.js
Solution2.js
Jan 13, 2024
Solution2.py
Solution2.py
Jan 13, 2024

README.md

comments difficulty edit_url
true
困难

面试题 19. 正则表达式匹配

题目描述

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

注意：本题与主站 10 题相同：https://leetcode.cn/problems/regular-expression-matching/

解法

方法一：记忆化搜索

我们设计一个函数 d f s ( i , j ) ，表示从 s 的第 i 个字符开始，和 p 的第 j 个字符开始是否匹配。那么答案就是 d f s ( 0 , 0 ) 。

函数 d f s ( i , j ) 的计算过程如下：

  • 如果 j 已经到达 p 的末尾，那么如果 i 也到达了 s 的末尾，那么匹配成功，否则匹配失败。
  • 如果 j 的下一个字符是 '*'，我们可以选择匹配 0 个 s [ i ] 字符，那么就是 d f s ( i , j + 2 ) 。如果此时 i < m 并且 s [ i ] 和 p [ j ] 匹配，那么我们可以选择匹配 1 个 s [ i ] 字符，那么就是 d f s ( i + 1 , j ) 。
  • 如果 j 的下一个字符不是 '*'，那么如果 i < m 并且 s [ i ] 和 p [ j ] 匹配，那么就是 d f s ( i + 1 , j + 1 ) 。否则匹配失败。

过程中，我们可以使用记忆化搜索，避免重复计算。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别是 s 和 p 的长度。

Python3

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)

Java

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;
    }
}

C++

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);
    }
};

Go

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)
}

JavaScript

/**
 * @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);
};

C#

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;
    }
}

Swift

class Solution {
    private var memo: [[Bool?]] = []
    private var s: [Character] = []
    private var p: [Character] = []
    private var m: Int = 0
    private var n: Int = 0

    func isMatch(_ s: String, _ p: String) -> Bool {
        self.s = Array(s)
        self.p = Array(p)
        self.m = s.count
        self.n = p.count
        self.memo = Array(repeating: Array(repeating: nil, count: n + 1), count: m + 1)
        return dfs(0, 0)
    }

    private func dfs(_ i: Int, _ j: Int) -> Bool {
        if j >= n {
            return i == m
        }
        if let res = memo[i][j] {
            return res
        }
        var res = false
        if j + 1 < n && p[j + 1] == "*" {
            res = dfs(i, j + 2) || (i < m && (s[i] == p[j] || p[j] == ".") && dfs(i + 1, j))
        } else {
            res = i < m && (s[i] == p[j] || p[j] == ".") && dfs(i + 1, j + 1)
        }
        memo[i][j] = res
        return res
    }
}

方法二：动态规划

我们可以将方法一中的记忆化搜索转换为动态规划。

定义 f [ i ] [ j ] 表示字符串 s 的前 i 个字符和字符串 p 的前 j 个字符是否匹配。那么答案就是 f [ m ] [ n ] 。初始化 f [ 0 ] [ 0 ] = t r u e ，表示空字符串和空正则表达式是匹配的。

与方法一类似，我们可以分情况来讨论。

  • 如果 p [ j − 1 ] 是 '*'，那么我们可以选择匹配 0 个 s [ i − 1 ] 字符，那么就是 f [ i ] [ j ] = f [ i ] [ j − 2 ] 。如果此时 s [ i − 1 ] 和 p [ j − 2 ] 匹配，那么我们可以选择匹配 1 个 s [ i − 1 ] 字符，那么就是 f [ i ] [ j ] = f [ i ] [ j ] ∨ f [ i − 1 ] [ j ] 。
  • 如果 p [ j − 1 ] 不是 '*'，那么如果 s [ i − 1 ] 和 p [ j − 1 ] 匹配，那么就是 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] 。否则匹配失败。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别是 s 和 p 的长度。

Python3

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]

Java

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];
    }
}

C++

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];
    }
};

Go

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]
}

JavaScript

/**
 * @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];
};

C#

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];
    }
}