算法练习——正则表达式匹配

2021年1月3日,跨完年回到宿舍,开始了我的新旅途,开启算法的练习,今天练习的是LeetCode的第10题:正则表达式匹配。在练习这一题的时候,看完题很快就有了思路,通过一个游标来扫描,按照.*对应的规则进行匹配,注意:这是未通过的代码,详细代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public boolean isMatch(String s, String p) {
int sCur = 0;
char pre = '.';
char[] sChars = s.toCharArray(), pChars = p.toCharArray();
for (int i = 0; i < pChars.length; i++) {
char c = pChars[i];
if (c == '*') {
if (pre == '.') return true;
while (sCur < sChars.length) {
if (sChars[sCur] != pre) {
break;
}
sCur++;
}
continue;
}
char sc = sChars[sCur];
if (c == '.' || c == sc) {
sCur++;
} else if (pChars[i + 1] != '*') {
return false;
}
pre = c;
}
return sCur == sChars.length;
}
}

结果并没有通过,能通过部分测试用例,大概是部分条件没有涵盖到,并且有部分逻辑冲突,找了半个小时都没有修改成功。于是去查看题解,发现这题能够通过动态规划或是递归解决,这也是我所欠缺的,不会运用递归,每一个问题首先想到的都是循环,并非递归。

记录这篇文章是希望能够将这些练习的一些过程、心得记录下来,在自己难以坚持的时候能从这些记录中看到自己的进步,获得使自己坚持下去的动力支撑。今日的算法练习便在此结束,在今后的算法练习中,应当更多的去思考递归,运用递归思想。最后附上这题我觉得一个比较好的题解,一步一步从递归到动态规划的题解