最近，一直在想一个问题：为什么在大环境这么差的情况下，反而离职的人越来越多？是不是有点反常？🤔
回头看看我的工作圈，最近不少人选择了离职。
比如原团队六个人，结果裁了三个人，剩下三个人就得把六个人的活都干了。说实话，这种情况很常见。
大环境经济低迷，很多公司选择裁员来压缩成本，但裁员带来的并不只是人少了那么简单。
剩下的人不仅要承担更多的工作，还得面对更高的压力——因为谁不想留在公司呢？大家都开始卷了，想着做得更好，自己才能保住饭碗，但其实压力就更大了。
于是，这个“卷”的环境让大家的生存状态变得更差。
很多人开始思考：与其继续在这种环境里“卷”下去，不如换个地方，至少心情好一些，对吧？💼
有时候我也会想，为什么自己不离职？不过一想到没多少选择，还是继续忍吧~
与其卷离职不如卷技术，提升技术能力总是没错的，所以算法题我们继续走起！
算法题：通配符匹配
嗨，大家好！今天咱们来聊聊一个挺经典的算法题：通配符匹配。
相信很多人见过类似的题目，尤其是在面试中，关于字符串匹配的题目永远不会过时。无论是为了大厂面试，还是为了刷题提升，通配符匹配都可以算得上是一个“老大难”问题。
首先，什么是通配符匹配？通配符匹配，顾名思义，就是通过一些特定的符号（通配符）来匹配字符串。比如常见的“*”和“？”这两种符号：
“？”可以匹配任意单个字符 “*”可以匹配零个或多个字符
举个例子，假设我们有一个模式 s = "a*b?c"，这个模式就可以匹配如 abxxc、a123bcd 这类符合规则的字符串。那么问题来了，如何实现一个算法，判断一个字符串是否符合给定的通配符模式呢？
思路分析
我们可以通过动态规划（DP）来解决这个问题。动态规划的核心思路是构建一个表格（二维数组），每个元素记录当前字符串和模式是否能够匹配。我们可以定义一个二维的DP数组 dp[i][j]，其中 i 表示字符串的前 i 个字符，j 表示模式的前 j 个字符。
对于字符串 s 和模式 p，我们可以根据以下几种情况来填充 dp 数组：
如果模式中的当前字符是“？”或是字符串中的字符，且它们匹配，那么 dp[i][j]就由dp[i-1][j-1]来决定。如果模式中的当前字符是“*”，它可以匹配零个或多个字符。我们需要分别考虑：
“*”匹配零个字符，此时我们看 dp[i][j-1]“*”匹配一个或多个字符，此时我们看 dp[i-1][j]
DP 状态转移方程
首先，我们需要初始化 dp[0][0] 为 true，因为空字符串和空模式是匹配的。
然后，根据上面的分析，状态转移方程可以写成：
如果模式的当前字符是普通字符或“？”并且匹配，那么： dp[i][j] = dp[i-1][j-1]如果模式的当前字符是“*”，那么： dp[i][j] = dp[i-1][j] || dp[i][j-1]
代码实现
下面是我用 Java 写的通配符匹配算法的代码实现：
public class WildcardMatching {
public boolean isMatch(String s, String p) {
// dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
// 空字符串和空模式是匹配的
dp[0][0] = true;
// 初始化 dp 数组，当模式 p 中有 * 的时候，dp[i][0] 应该为 false
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// 填充 dp 数组
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
char sc = s.charAt(i - 1);
char pc = p.charAt(j - 1);
if (pc == sc || pc == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (pc == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
// 最终返回 dp[s.length()][p.length()]
return dp[s.length()][p.length()];
}
public static void main(String[] args) {
WildcardMatching matcher = new WildcardMatching();
System.out.println(matcher.isMatch("aa", "a*")); // 输出 true
System.out.println(matcher.isMatch("mississippi", "mis*is*p*.")); // 输出 false
}
}
代码解析
初始化：首先我们创建了一个二维数组
dp，用于记录每一对字符串和模式是否匹配。然后我们初始化了当模式为空时，dp[0][0] = true，表示空字符串和空模式是匹配的。**处理
***：我们处理了模式中的*，它可以匹配零个或多个字符。所以在dp[0][j]中，只有当p[j-1] == '*'时，dp[0][j]才会是true，表示模式前缀只由*构成时，可以匹配空字符串。递推：接着通过双层循环填充
dp数组，对于每一个字符，我们根据当前字符是?、*还是普通字符来决定dp[i][j]的值。最终结果：最后，我们返回
dp[s.length()][p.length()]，即字符串和模式完全匹配的结果。
总结
通配符匹配问题看似简单，但实际上涉及到的边界条件和状态转移需要仔细考虑。通过动态规划，我们可以高效地解决这个问题，时间复杂度为 O(m * n)，其中 m 是字符串的长度，n 是模式的长度。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
