剑指Offer:正则表达式匹配
题目
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配。
思路 + 代码
动态规划:利用一个dp(x, y)的数组表示原字符串 s[0, x) 与匹配字符串 p[0, y)是否匹配。
状态转移:
对于dp(x, y):
如果 p(y) == ‘.’ || p(y) == s(x-1), dp(x, y)
= dp(x-1, y-1)。如果 p(y) == ‘*’
2.1 如果 p(y-1) == s(x) || p(y-1) == ‘.’
1) ‘‘ 复制多个:dp(x, y) = dp(x-1, y)
2) ‘‘ 复制一个:dp(x, y) = dp(x, j-1)
3) ‘*’ 复制零个:dp(x, y) = dp(x, j-2)2.2 如果 s 为空且不满足 2.1,则 ‘*’ 复制零个:dp(x, y) = dp(x, j-2)
1 | public class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 孙云增的博客!
评论