实现 SQL LIKE 通配符匹配(% 与 _)
哪些公司问过
答案要点
- % 匹配任意长度(含空)序列,_ 匹配恰好一个字符
- dp[i][j]:s 前 i 个与 p 前 j 个是否匹配
- %:dp[i][j-1] 或 dp[i-1][j]
- _ 或字符相等:dp[i-1][j-1]
- dp[0][0] 为真,空串只能被前缀全为 % 的模式匹配
易错点
- 把百分号当成只匹配非空序列
- 连续多个百分号的情况没有正确处理
- 忘记 LIKE 要求整串匹配,写成了子串查找
面试官常见追问
- 有没有比 DP 更省空间的做法?
- 数据库里 LIKE 什么情况下能用索引?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场