java数据结构与算法刷题-----LeetCode10：正则表达式匹配

1. 思路分析

动态规划，依次遍历正则，看看当前正则是否可以匹配当前长度的字符串。具体看代码注释。比如"ac"和".*“匹配，先"空串"匹配"空串”，然后"a"匹配".“，然后"a"匹配”. * “，然后"ac"匹配”.",“ac"匹配”. * "。

2. 代码
   

class Solution {
    /**isMatch("aacc", ".*c*")
     *              ""      "."     ".*"    ".*c"   ".*c*"  每个下标对应的正则串
     *              ""      .       *        c        *
     *              0       1       2        3        4
     * ""     "" 0  true    false   true    false   true    第一行，s""匹配p""必定为true。s""匹配p正则，有可能是true，比如".*"
     * "a"     a 1  false   true    true    false   true
     * "aa"    a 2  false   false   true    false   true
     * "aac"   c 3  false
     * "aacc"  c 4  false
     *
     * 每个下标对应的字符串
     *
     * ==============第二行解析
     * i=1,j=1 ："a"匹配"."。.匹配任意一个字符。因此匹配成功，可以将a和.抵消掉。变成"空串"匹配"空串"。也就是dp[0][0] = true
     * i=1,j=2 ："a"匹配".*"。
     *      *可以匹配前面一个字符0个或多个。前面是"."
     *          匹配0个任意字符，那么".*"不会抵消任何字符串，因此可以将匹配看成"a"匹配""，也就是dp[1][0] = false
     *          匹配任意个字符，可以先从匹配一个开始
     *              抵消一个a变成：""匹配".*"。也就是dp[0][2] = true。因此可以匹配成功
     * i=1,j=3："a"匹配".*c"
     *      c只能匹配s末尾的c，"a"和"c"不匹配，为false
     * i=1,j=4："a"匹配".*c*"
     *      *，前面是c
     *          匹配0个，c*就相当于不存在。可以看成"a"匹配".*",也就是dp[i][2] = true
     *          匹配多个
     *              先抵消末尾元素"a"匹配"c"，发现末尾元素压根不相等
     *              只能匹配0次
     * ==============第三行解析
     * i=2,j=1 ："aa"匹配"."。
     *      .匹配任意一个字符，因此"."和一个"a"抵消。可以看成"a"匹配""。也就是dp[1][0] = false
     * i=2,j=2 ："aa"匹配".*"。
     *      *前面是"."，不用考虑末尾是否相等问题
     *          *匹配0个，也就是"aa"=>>>""。也就是dp[2][0] = false
     *          *匹配多个，先匹配一个,抵消一个"a"。也就是"a"=>>>".*",dp[1][2] = true;
     * i=2,j=3："aa"匹配".*c"
     *      c只能匹配末尾的c，"a"!="c"，不匹配 = false
     * i=2,j=4："aa"匹配".*c*"
     *      前面是c，c!=a。末尾不匹配。只能匹配0个
     *          匹配0个c变成，"aa"===>>>>".*" dp[2][2] = true;
     *  以此类推即可
     */
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pstr = p.toCharArray();
        boolean[][] dp = new boolean[str.length + 1][pstr.length + 1];
        //初始化第一行，s""匹配p""必定为true。s""匹配p正则，有可能是true，比如".*"
        dp[0][0] = true;//s""匹配p""必定为true
        //s""匹配p正则，有可能是true，比如".*"。总结规律，第一行，""匹配时，只考虑*的情况即可。因为""不能匹配"a","b","."等等，
        //而有了*，可以匹配0个，比如"a*",就可以匹配成""
        for (int i = 0; i < pstr.length; i++) {
            //""匹配".*"为例，.*匹配0个，相当于，""==>>>"",也就是dp[0][2-2]。也就是dp[0][2] = dp[0][0]
            if(pstr[i]=='*') dp[0][i+1] = dp[0][i-1];//i是字符串下标，dp[0]保存的是空串的状态，因此，和字符串下标i有1个偏差
        }
        //开始剩余行填充
        for (int i = 0; i < str.length; i++) {
            for (int j = 0; j < pstr.length; j++) {
                //单个字符，并且可以匹配，或者为一个"."。比如"a"===>>>"a"或"a"===>>>"."，都可以抵消一个a，就变成""===>>>""
                if(str[i]==pstr[j]||pstr[j]=='.'){
                    //"a"==>"."变成""===>>>"",也就是dp[1][1] = dp[0][0]。下标相差1
                    dp[i+1][j+1] = dp[i][j];
                }else if(pstr[j]=='*'){//如果是'*'
                    //先判断前一个字符是否是单个字符，并且可以末尾匹配成功，或者是"."
                    if(str[i]==pstr[j-1]||pstr[j-1]=='.'){
                        //匹配0次，"a"===>>".*"变成"a"===>>>"" 也就是dp[1][2]===>>dp[1][0]
                        dp[i+1][j+1] = dp[i+1][j-1]
                                //匹配多次，先匹配一个变成""====>>>".*"也就是dp[1][2]====>>>dp[0][2]
                                ||dp[i][j+1];
                    }else{//如果末尾字符串不匹配，比如"a"===>"c*",那就只能匹配0次，变成"a"==>>>"",也就是dp[1][2]===>>>dp[1][0]
                        dp[i+1][j+1] = dp[i+1][j-1];
                    }
                }
            }
        }
        return dp[str.length][pstr.length];
    }
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

刷题一定要坚持，总结套路，不单单要把题做出来，要举一反三，也要参考别人的思路，学习别人解题的优点，找出你觉得可以优化的点。

1. 单链表解题思路：双指针、快慢指针、反转链表、预先指针

1. 双指针：对于单链表而言，可以方便的让我们遍历结点，并做一些额外的事
2. 快慢指针：常用于找链表中点，找循环链表的循环点，一般快指针每次移动两个结点，慢指针每次移动一个结点。
3. 反转链表：通常有些题，将链表反转后会更好做，一般选用三指针迭代法，递归的空间复杂度有点高
4. 预先指针：常用于找结点，比如找倒数第3个结点，那么定义两个指针，第一个指针先移动3个结点，然后两个指针一起遍历，当第一个指针遍历完成，第二个指针指向的结点就是要找的结点

2. 数组解题思路：双指针、三指针，下标标记

1. 双指针：多用于减少时间复杂度，快速遍历数组
2. 三指针：多用于二分查找，分为中间指针，左和右指针
3. 下标标记：常用于在数组范围内找东西，而不想使用额外的空间的情况，比如找数组长度为n，元素取值范围为[1,n]的数组中没有出现的数字，遍历每个元素，然后将对应下标位置的元素变为负数或者超出[1,n]范围的正数，最后没有发生变化的元素，就是缺少的值。
4. 差分数组：对差分数组求前缀和即可得到原数组

1. 用差值，作为下标，节省空间找东西。比如1900年到2000年，就可以定义100大小的数组，每个数组元素下标的查找为1900。
2. 前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 ii个数即为原数组的第 i-1 个元素和第 i个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组

5. 前缀和：假设有一个数组arr[1,2,3,4]。然后创建一个前缀和数组sum，记录从开头到每个元素区间的和。第一个元素是0。第二个元素，保存第一个和sum[1] = sum[0]+arr[0]，第二个元素，保存第二个和sum[2] = sum[1]+arr[1]

3. 栈解题思路：倒着入栈，双栈

1. 倒着入栈：适用于出栈时想让输出是正序的情况。比如字符串’abc’，如果倒着入栈，那么栈中元素是（c,b,a）。栈是先进后出，此时出栈，结果为abc。
2. 双栈：适用于实现队列的先入先出效果。一个栈负责输入，另一个栈负责输出。