【算法】正则表达式匹配

发表于 阅读次数：

剑指 Offer 第 19 题-正则表达式匹配

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含 0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

数据范围:

  • 1.str 可能为空，且只包含从 a-z 的小写字母。
  • 2.pattern 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。
  • 3.1 <= str.length <= 20
  • 4.1 <= pattern.length <= 30

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

方法 1

在原数组上，移动下标，合并边界

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

/**
 * 描述
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 * <p>
 * 数据范围:
 * 1.str 可能为空，且只包含从 a-z 的小写字母。
 * 2.pattern 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
 * 3.1 <= str.length <= 20
 * 4.1 <= pattern.length <= 30
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * @author lilou
 */
public class Jz19_1 {
    public static void main(String[] args) {
        final Jz19_1 jz19 = new Jz19_1();
        jz19.test("Test22", "aaa", "ab*a", false);

        jz19.test("Test01", "", "", true);
        jz19.test("Test02", "", ".*", true);
        jz19.test("Test03", "", ".", false);
        jz19.test("Test04", "", "c*", true);
        jz19.test("Test05", "a", ".*", true);
        jz19.test("Test06", "a", "a.", false);
        jz19.test("Test07", "a", "", false);
        jz19.test("Test08", "a", ".", true);
        jz19.test("Test09", "a", "ab*", true);
        jz19.test("Test10", "a", "ab*a", false);
        jz19.test("Test11", "aa", "aa", true);
        jz19.test("Test12", "aa", "a*", true);
        jz19.test("Test13", "aa", ".*", true);
        jz19.test("Test14", "aa", ".", false);
        jz19.test("Test15", "ab", ".*", true);
        jz19.test("Test16", "ab", ".*", true);
        jz19.test("Test17", "aaa", "aa*", true);
        jz19.test("Test18", "aaa", "aa.a", false);
        jz19.test("Test19", "aaa", "a.a", true);
        jz19.test("Test20", "aaa", ".a", false);
        jz19.test("Test21", "aaa", "a*a", true);
        jz19.test("Test22", "aaa", "ab*a", false);
        jz19.test("Test23", "aaa", "ab*ac*a", true);
        jz19.test("Test24", "aaa", "ab*a*c*a", true);
        jz19.test("Test25", "aaa", ".*", true);
        jz19.test("Test26", "aab", "c*a*b", true);
        jz19.test("Test27", "aaca", "ab*a*c*a", true);
        jz19.test("Test28", "aaba", "ab*a*c*a", false);
        jz19.test("Test29", "bbbba", ".*a*a", true);
        jz19.test("Test30", "bcbbabab", ".*a*a", false);
    }

    private void test(String testName, String str, String pattern, boolean expired) {
        if (match(str, pattern) == expired) {
            return;
        }
        System.out.printf("%s 结果不对\n", testName);
    }

    public boolean match(String str, String pattern) {

        // 串和模式为空的判断
        if (str == null && pattern == null) {
            return true;
        }
        if (str == null || pattern == null) {
            return false;
        }

        // 转换为char数组
        final char[] strArr = str.toCharArray();
        final char[] patternArr = pattern.toCharArray();
        int strIndex = 0;
        int patternIndex = 0;
        // 进入递归
        return matchCore(strArr, strIndex, patternArr, patternIndex);
    }


    private boolean matchCore(char[] strArr, int strIndex, char[] patternArr, int patternIndex) {

        // 模式匹配到最后了，就可以决定串是否匹配
        if (isEnd(patternArr, patternIndex)) {
            return isEnd(strArr, strIndex);
        }

        // 如果串的第一个字符不存在，
        // 假如串是「aa」，模式是「aaa*」
        // 可以向下进行，判断模式串是不是「.*」或「a*」

        // 如果串的第一个字符存在
        // 判断串的第一个字符是否和模式的第一个字符匹配
        boolean firstMatch = !isEnd(strArr, strIndex) && (
                patternArr[patternIndex] == '.' || patternArr[patternIndex] == strArr[strIndex]);

        // 判断模式的第二个字符是不是「*」
        if ((patternIndex + 1 < patternArr.length) && (patternArr[patternIndex + 1] == '*')) {
            // 模式串右移2位 或 字符串移动1
            return matchCore(strArr, strIndex, patternArr, patternIndex + 2) ||
                    (firstMatch && matchCore(strArr, strIndex + 1, patternArr, patternIndex));
        } else {
            return firstMatch && matchCore(strArr, strIndex + 1, patternArr, patternIndex + 1);
        }
    }

    private final char END = '\0';

    private boolean isEnd(char[] arr, int index) {
        return END == indexArr(arr, index);
    }

    private char indexArr(char[] arr, int index) {
        if (index < arr.length) {
            return arr[index];
        }
        return END;
    }

}

方法 2

在原数组上，移动下标，列出详细的边界

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
public class Jz19_2 {
    public static void main(String[] args) {
        final Jz19_2 jz19 = new Jz19_2();
        jz19.test("Test22", "aaa", "ab*a", false);

        jz19.test("Test01", "", "", true);
        jz19.test("Test02", "", ".*", true);
        jz19.test("Test03", "", ".", false);
        jz19.test("Test04", "", "c*", true);
        jz19.test("Test05", "a", ".*", true);
        jz19.test("Test06", "a", "a.", false);
        jz19.test("Test07", "a", "", false);
        jz19.test("Test08", "a", ".", true);
        jz19.test("Test09", "a", "ab*", true);
        jz19.test("Test10", "a", "ab*a", false);
        jz19.test("Test11", "aa", "aa", true);
        jz19.test("Test12", "aa", "a*", true);
        jz19.test("Test13", "aa", ".*", true);
        jz19.test("Test14", "aa", ".", false);
        jz19.test("Test15", "ab", ".*", true);
        jz19.test("Test16", "ab", ".*", true);
        jz19.test("Test17", "aaa", "aa*", true);
        jz19.test("Test18", "aaa", "aa.a", false);
        jz19.test("Test19", "aaa", "a.a", true);
        jz19.test("Test20", "aaa", ".a", false);
        jz19.test("Test21", "aaa", "a*a", true);
        jz19.test("Test22", "aaa", "ab*a", false);
        jz19.test("Test23", "aaa", "ab*ac*a", true);
        jz19.test("Test24", "aaa", "ab*a*c*a", true);
        jz19.test("Test25", "aaa", ".*", true);
        jz19.test("Test26", "aab", "c*a*b", true);
        jz19.test("Test27", "aaca", "ab*a*c*a", true);
        jz19.test("Test28", "aaba", "ab*a*c*a", false);
        jz19.test("Test29", "bbbba", ".*a*a", true);
        jz19.test("Test30", "bcbbabab", ".*a*a", false);
    }

    private void test(String testName, String str, String pattern, boolean expired) {
        if (match(str, pattern) == expired) {
            return;
        }
        System.out.printf("%s 结果不对\n", testName);
    }

    public boolean match(String str, String pattern) {

        // 串和模式为空的判断
        if (str == null && pattern == null) {
            return true;
        }
        if (str == null || pattern == null) {
            return false;
        }

        // 转换为char数组
        final char[] strArr = str.toCharArray();
        final char[] patternArr = pattern.toCharArray();
        int strIndex = 0;
        int patternIndex = 0;
        // 进入递归
        return matchCore(strArr, strIndex, patternArr, patternIndex);
    }


    private boolean matchCore(char[] strArr, int strIndex, char[] patternArr, int patternIndex) {

        // 1. 串或模式边界的判断
        // 串和模式都匹配到最后了: ("", "")
        if (isEnd(strArr, strIndex) && isEnd(patternArr, patternIndex)) {
            return true;
        }

        // 2. 模式已经匹配到最后了，串还有: ("a", "")
        if (!isEnd(strArr, strIndex) && isEnd(patternArr, patternIndex)) {
            return false;
        }

        // 3. 串已经匹配到最后了，模式还有
        if (isEnd(strArr, strIndex) && !isEnd(patternArr, patternIndex)) {
            // 串已经匹配到最后了，模式还有情况1("", ".*")
            if (!isEnd(patternArr, patternIndex + 1)) {
                return matchCore(strArr, strIndex, patternArr, patternIndex + 2);
            }
            // 串已经匹配到最后了，情况2 ("", ".")、("", "a")、("", "..")
            return false;
        }

        // 4. 模式和串都还有

        // 提前校验一下 patternIndex+1
        // 4.1 下一个模式字符没有了（"a", "."）、（"a", "a"）、（"aa", "a"）
        if (isEnd(patternArr, patternIndex + 1)) {
            // 下一个串字符是否还有
            if (!isEnd(strArr, strIndex + 1)) {
                return false;
            }

            // 比较当前的串和模式字符
            return patternArr[patternIndex] == '.' || patternArr[patternIndex] == strArr[strIndex];
        }

        // 4.2 pattern的第2个字符不为*
        final char secondPatternChar = patternArr[patternIndex + 1];
        if ((secondPatternChar != '*')) {
            // 4.2.1 比较串和模式的第一个字符，第一个模式字符是「.」，或串和模式相等，则匹配下一个字符
            if (patternArr[patternIndex] == '.' || patternArr[patternIndex] == strArr[strIndex]) {
                return matchCore(strArr, strIndex + 1, patternArr, patternIndex + 1);
            }
            // 4.2.2 否则直接不匹配
            return false;
        }

        if (patternArr[patternIndex] == '.' || patternArr[patternIndex] == strArr[strIndex]) {
            // 4.3 pattern的第2个字符为「*」，如：(aa, a*)
            // 模式串右移2位 或 字符串移动1
            return matchCore(strArr, strIndex, patternArr, patternIndex + 2) ||
                    // matchCore(strArr, strIndex + 1, patternArr, patternIndex + 2) ||
                    matchCore(strArr, strIndex + 1, patternArr, patternIndex);
        } else {
            return matchCore(strArr, strIndex, patternArr, patternIndex + 2);
        }
    }

    private final char END = '\0';

    private boolean isEnd(char[] arr, int index) {
        return END == indexArr(arr, index);
    }

    private char indexArr(char[] arr, int index) {
        if (index < arr.length) {
            return arr[index];
        }
        return END;
    }

}

方法 3

拆出新数组，合并边界

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public class Jz19_3 {
    public static void main(String[] args) {
        final Jz19_3 jz19 = new Jz19_3();
        jz19.test("Test22", "aaa", "ab*a", false);

        jz19.test("Test01", "", "", true);
        jz19.test("Test02", "", ".*", true);
        jz19.test("Test03", "", ".", false);
        jz19.test("Test04", "", "c*", true);
        jz19.test("Test05", "a", ".*", true);
        jz19.test("Test06", "a", "a.", false);
        jz19.test("Test07", "a", "", false);
        jz19.test("Test08", "a", ".", true);
        jz19.test("Test09", "a", "ab*", true);
        jz19.test("Test10", "a", "ab*a", false);
        jz19.test("Test11", "aa", "aa", true);
        jz19.test("Test12", "aa", "a*", true);
        jz19.test("Test13", "aa", ".*", true);
        jz19.test("Test14", "aa", ".", false);
        jz19.test("Test15", "ab", ".*", true);
        jz19.test("Test16", "ab", ".*", true);
        jz19.test("Test17", "aaa", "aa*", true);
        jz19.test("Test18", "aaa", "aa.a", false);
        jz19.test("Test19", "aaa", "a.a", true);
        jz19.test("Test20", "aaa", ".a", false);
        jz19.test("Test21", "aaa", "a*a", true);
        jz19.test("Test22", "aaa", "ab*a", false);
        jz19.test("Test23", "aaa", "ab*ac*a", true);
        jz19.test("Test24", "aaa", "ab*a*c*a", true);
        jz19.test("Test25", "aaa", ".*", true);
        jz19.test("Test26", "aab", "c*a*b", true);
        jz19.test("Test27", "aaca", "ab*a*c*a", true);
        jz19.test("Test28", "aaba", "ab*a*c*a", false);
        jz19.test("Test29", "bbbba", ".*a*a", true);
        jz19.test("Test30", "bcbbabab", ".*a*a", false);
    }

    private void test(String testName, String str, String pattern, boolean expired) {
        if (match(str, pattern) == expired) {
            return;
        }
        System.out.printf("%s 结果不对\n", testName);
    }

    public boolean match(String str, String pattern) {

        // 串和模式为空的判断
        if (str == null && pattern == null) {
            return true;
        }
        if (str == null || pattern == null) {
            return false;
        }

        // 转换为char数组
        final char[] strArr = str.toCharArray();
        final char[] patternArr = pattern.toCharArray();
        // 进入递归
        return matchCore(strArr, patternArr);
    }


    private boolean matchCore(char[] strArr, char[] patternArr) {

        // 模式到最后了，看串是否还有（没有则匹配，有则不匹配）
        if (isEmptyArr(patternArr)) {
            return isEmptyArr(strArr);
        }

        // 串的第一个字符存在，且模式的第一个字符匹配串的第一个字符
        final boolean firstMatch = !isEmptyArr(strArr) &&
                (patternArr[0] == '.' || patternArr[0] == strArr[0]);

        // 模式串第2位为*
        if (patternArr.length >= 2 && patternArr[1] == '*') {
            // 不论第一个是否匹配，模式串后移2位
            return matchCore(strArr, subArr(2, patternArr)) ||
                    // 或者，如果第一个匹配，串后移一位
                    (firstMatch && matchCore(subArr(1, strArr), patternArr));
        }

        // 其它情况，要求第一个匹配，且后面的也匹配
        return firstMatch && matchCore(subArr(1, strArr), subArr(1, patternArr));
    }

    private boolean isEmptyArr(char[] arr) {
        return arr == null || arr.length == 0;
    }

    private char[] subArr(int start, char[] arr) {
        return Arrays.copyOfRange(arr, start, arr.length);
    }

}