DOS时代通配符解析与LeetCode 44. Wildcard Matching

"这篇文档主要讨论了从代码的角度理解DOS时代通配符，并通过LeetCode的44题‘Wildcard Matching’来探讨正则匹配问题。作者Jimbowhy分享了他在实现一个简单的正则匹配工具过程中的思考和解题经验。文章详细分析了如何用O(N)的时间复杂度解决字符串匹配问题，特别关注'?'和'*'这两个通配符的处理。" 在这篇文档中，作者首先提到了LeetCode的44题——Wildcard Matching，这是一个关于字符串匹配的难题，要求实现支持'?'和'*'两种通配符的功能。'?'代表任何单个字符，'*'则能匹配任意长度的字符序列，包括空序列。匹配需覆盖整个输入字符串而非部分。题目提供了一个名为`isMatch`的函数原型，用于判断给定的字符串`s`是否匹配模式`p`。 作者指出，此题虽然难度低于完整的正则表达式实现，但它是锻炼正则表达式匹配技巧的良好实践。他还提到了另一道类似题目——"10.RegularExpressionMatching"，该题只涉及'.*'两个通配符，其中'.'相当于'?'，而'*'表示零或多个前一个字符。这两题难度相当，但正则表达式的题目可能更受欢迎一些。 在解题策略上，作者考虑了线性扫描方法，即遍历输入字符串一次来完成匹配。然而，处理'*'通配符的复杂性在于它可能匹配零个或多个字符，这就需要回溯机制来确定所有可能的匹配情况。为了达到O(N)的时间复杂度，通常会采用动态规划或者递归的方法来设计解决方案。 动态规划的方法是创建一个二维布尔数组，用来记录到当前位置为止字符串`s`和模式`p`是否匹配。状态转移方程可以这样定义：如果当前字符都匹配（非'?'或'*'的情况），则下一个位置匹配；如果模式中的字符是'?'，则下一个位置的匹配不论当前字符串的字符是什么；如果模式字符是'*'，则有两种情况，一是忽略'*'前面的字符，继续匹配后面的字符，二是保留'*'前面的字符，允许'*'匹配空字符。 递归的思路则是从字符串末尾开始，向前推进，对于每个位置，根据当前模式字符是'?'、'*'还是普通字符，递归地判断后续字符的匹配情况。 无论是动态规划还是递归，都需要处理边界条件和特殊情况，例如空字符串的匹配、'*'位于模式开头或结尾的情况等。这两种方法都能有效地解决这个问题，但也需要谨慎处理递归深度和空间复杂度，以防止超时或超出内存限制。 通过解决LeetCode的44题，读者不仅可以了解到DOS时代的通配符匹配原理，还能深入理解正则表达式的基础以及如何在实际编程中实现高效字符串匹配算法。这对于提升编程能力和算法理解具有很大的帮助。