forked from Wang-Jun-Chao/coding-interviews
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTest53.java
More file actions
123 lines (104 loc) · 4.55 KB
/
Test53.java
File metadata and controls
123 lines (104 loc) · 4.55 KB
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
/**
* Author: 王俊超
* Date: 2015-06-15
* Time: 09:19
* Declaration: All Rights Reserved !!!
*/
public class Test53 {
/**
* 题目：请实现一个函数用来匹配包含‘.’和‘*’的正则表达式。模式中的字符'.'表示任意一个字符，
* 而‘*’表示它前面的字符可以出现任意次（含0次）。本题中，匹配是指字符串的所有字符匹配整个模式。
*
* @param input
* @param pattern
* @return
*/
public static boolean match(String input, String pattern) {
if (input == null || pattern == null) {
return false;
}
return matchCore(input, 0, pattern, 0);
}
private static boolean matchCore(String input, int i, String pattern, int p) {
// 匹配串和模式串都到达尾，说明成功匹配
if (i >= input.length() && p >= pattern.length()) {
return true;
}
// 只有模式串到达结尾，说明匹配失败
if (i != input.length() && p >= pattern.length()) {
return false;
}
// 模式串未结束，匹配串有可能结束有可能未结束
// p位置的下一个字符中为*号
if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
// 匹配串已经结束
if (i >= input.length()) {
return matchCore(input, i, pattern, p + 2);
}
// 匹配串还没有结束
else {
if (pattern.charAt(p) == input.charAt(i) || pattern.charAt(p) == '.') {
return
// 匹配串向后移动一个位置，模式串向后移动两个位置
matchCore(input, i + 1, pattern, p + 2)
// 匹配串向后移动一个位置，模式串不移动
|| matchCore(input, i + 1, pattern, p)
// 匹配串不移动，模式串向后移动两个位置
|| matchCore(input, i, pattern, p + 2);
} else {
return matchCore(input, i, pattern, p + 2);
}
}
}
//
// 匹配串已经结束
if (i >= input.length()) {
return false;
}
// 匹配串还没有结束
else {
if (input.charAt(i) == pattern.charAt(p) || pattern.charAt(p) == '.') {
return matchCore(input, i + 1, pattern, p + 1);
}
}
return false;
}
public static void main(String[] args) {
System.out.println(match("", "") + "[" + true + "]");
System.out.println(match("", ".*") + "[" + false + "]");
System.out.println(match("", ".") + "[" + false + "]");
System.out.println(match("", "c*") + "[" + true + "]");
System.out.println();
System.out.println(match("a", ".*") + "[" + true + "]");
System.out.println(match("a", "a.") + "[" + false + "]");
System.out.println(match("a", "") + "[" + false + "]");
System.out.println(match("a", ".") + "[" + true + "]");
System.out.println(match("a", "ab*") + "[" + true + "]");
System.out.println(match("a", "ab*a") + "[" + false + "]");
System.out.println();
System.out.println(match("aa", "aa") + "[" + true + "]");
System.out.println(match("aa", "a*") + "[" + true + "]");
System.out.println(match("aa", ".*") + "[" + true + "]");
System.out.println(match("aa", ".") + "[" + false + "]");
System.out.println();
System.out.println(match("ab", ".*") + "[" + true + "]");
System.out.println(match("ab", ".*") + "[" + true + "]");
System.out.println();
System.out.println(match("aaa", "aa*") + "[" + true + "]");
System.out.println(match("aaa", "aa.a") + "[" + false + "]");
System.out.println(match("aaa", "a.a") + "[" + true + "]");
System.out.println(match("aaa", ".a") + "[" + false + "]");
System.out.println(match("aaa", "a*a") + "[" + true + "]");
System.out.println(match("aaa", "ab*a") + "[" + false + "]");
System.out.println(match("aaa", "ab*ac*a") + "[" + true + "]");
System.out.println(match("aaa", "ab*a*c*a") + "[" + true + "]");
System.out.println(match("aaa", ".*") + "[" + true + "]");
System.out.println();
System.out.println(match("aab", "c*a*b") + "[" + true + "]");
System.out.println();
System.out.println(match("aaca", "ab*a*c*a") + "[" + true + "]");
System.out.println(match("aaba", "ab*a*c*a") + "[" + false + "]");
System.out.println(match("bbbba", ".*a*a") + "[" + true + "]");
System.out.println(match("bcbbabab", ".*a*a") + "[" + false + "]");
}
}