10. 正则表达式匹配：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 . 和 * 的正则表达式匹配。

• . 匹配任意单个字符
• * 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

样例 1：

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

样例 2：

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

样例 3：

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

提示：

• 1 <= s.length <= 20
• 1 <= p.length <= 30
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 如果从整个字符串去考虑，会有些迷茫。
• 用动态规划的思想，可以从0个字符到1个字符，再到2个字符，整个字符串的匹配情况依赖于去掉最后一个字符的匹配情况，以此类推。

题解

rust

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let s = s.as_bytes();
        let p = p.as_bytes();

        let match_c = |i, j| -> bool {
            i != 0 && (p[j - 1] == '.' as u8 || s[i - 1] == p[j - 1])
        };

        let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];
        dp[0][0] = true;
        (0..=s.len()).for_each(|i| {
            (1..=p.len()).for_each(|j| {
                dp[i][j] = if p[j - 1] == '*' as u8 {
                    match_c(i, j - 1) && dp[i - 1][j] || dp[i][j - 2]
                } else {
                    match_c(i, j) && dp[i - 1][j - 1]
                };
            })
        });

        dp[s.len()][p.len()]
    }
}

go

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
	matches := func(i, j int) bool {
		if i == 0 {
			return false
		}
		if p[j-1] == '.' {
			return true
		}
		return s[i-1] == p[j-1]
	}

	f := make([][]bool, m+1)
	for i := 0; i < len(f); i++ {
		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] || f[i][j-2]
				if matches(i, j-1) {
					f[i][j] = f[i][j] || f[i-1][j]
				}
			} else if matches(i, j) {
				f[i][j] = 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();
        int n = p.size();

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> f(m + 1, vector<int>(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 (matches(i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                } else {
                    if (matches(i, j)) {
                        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();
        int n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                char pc = p.charAt(j - 1);
                if (pc == '*') {
                    dp[i][j] = dp[i][j - 2]; // *匹配0次
                    if (i > 0 && !dp[i][j]) {
                        char prePc = p.charAt(j - 2);
                        if (prePc == '.'
                                || s.charAt(i - 1) == prePc) {
                            dp[i][j] = dp[i - 1][j]; // *匹配1次或多次
                        }
                    }
                } else if (i > 0 && (pc == '.' || s.charAt(i - 1) == pc)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
}

typescript

function isMatch(s: string, p: string): boolean {
    let m = s.length;
	let n = p.length;

	const matches = function (i: number, j: number): boolean {
		if (i == 0) {
			return false;
		}
		if (p[j - 1] == '.') {
			return true;
		}
		return s[i - 1] == p[j - 1];
	};

	let f = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 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] || f[i][j - 2];
				if (matches(i, j - 1)) {
					f[i][j] = f[i][j] || f[i - 1][j];
				}
			} else if (matches(i, j)) {
				f[i][j] = f[i][j] || f[i - 1][j - 1];
			}
		}
	}
	return f[m][n];
};

python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        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 matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~