前言本题为LeetCode中排名前100的高频题。我们社区会继续介绍谷一（NetflixGrowthHacker，《iOS 面试之道》作者，ACE专业健身教练。微博：@古香道长[1]）的Swift算法解法整理成文字版，方便大家的学习和阅读。到目前为止，我们已经更新了9期的LeetCode算法。我们会保持更新时间和进度（周一、周三、周五上午9:00发布）。每期内容不多。希望大家在上班的路上读一读，积累久了会有很大的提升。不积步，无以至万里；不积小流，则不成江海。Swift社区将陪伴您一路前行。难度等级：难1.描述一个已知字符串s和一个字符模式p，请实现一个支持'.'的正则表达式匹配。和'*'。'.'匹配任何单个字符'*'匹配前一个元素的零个或多个。所谓匹配就是覆盖整个字符串s，而不是字符串的一部分。2.示例示例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约束：1<=s.length<=201<=p.length<=30s可以为空，并且仅包含a-z中的小写字母。p可以为空，只包含小写字母a-z和字符.和*。保证每次出现一个字符*，都匹配一个有效字符3.答案classRegularExpressionMatching{funcisMatch(_s:String,_p:String)->Bool{letsChars=Array(s),pChars=Array(p)vardp=Array(重复：Array(repeating:false,count:pChars.count+1),count:sChars.count+1)dp[0][0]=trueforiin0...pChars.count{//jumpover""vs.x*"casedp[0][i]=i==0||i>1&&dp[0][i-2]&&pChars[i-1]=="*"}foriin0...sChars.count{forjin0...pChars.count{guardj>0else{continue}letpCurrent=pChars[j-1]ifpCurrent!="*"{dp[i][j]=i>0&&dp[i-1][j-1]&&(pCurrent=="."||pCurrent==sChars[i-1])}else{dp[i][j]=dp[i][j-2]||i>0&&j>1&&(sChars[i-1]==pChars[j-2]||pChars[j-2]==".")&&dp[i-1][j]}}}returndp[sChars.count][pChars.count]}}main思路：经典二维动态规划时间复杂度：O(mn)空间复杂度：O(mn)本算法解法库：LeetCode-Swift[2]去LeetCode[3]练习参考资料[1]@古迪道长：https://m.weibo.cn/u/1827884772[2]LeetCode-Swift：https://github.com/soapyigu/LeetCode-Swift[3]LeetCode：https://leetcode.com/problems/regular-expression-matching
