这个题看似简单,但是难度不小,jdk也有实现,但是自己来造轮子发现考虑的情况非常多,这次为了这个算法思考了两三天,最后找到了解决方案如下:
我们举个例子:aaabaa 与 a*b*aa 与 a*aabaa
首先反转字符数组,因为如果不翻转,遇到了字母都要去判断下一位是否是*,判断的时候还不能超越数组边界,而且下一位还可能还是这个字母,就是需要保留的位数,十分的麻烦,如果翻转了之后,星号后面肯定是有一个字符的。还要考虑跨越的中间的字符可能个数是否为零,为零后面的字符是否与前面的字符相等,如果相等,那被匹配的字符串还要至少保留对应的字符的个数,否则前面匹配完就无法匹配。说起来要考虑的因素非常多,还用到了异常处理,因为还有可能没考虑到的情况,这里属于异常情况就直接返回false,这样处理不一定合适,因为这要求你要控制住所有返回true的情况。
- public boolean match(char[] str,char[] pattern)
- {
- // 反转字符数组,因为如果不翻转,遇到了字母都要去判断下一位是否是*
- for (int i = str.length - 1,j = 0;j < i;i --,j ++) {
- char temp = str[i];
- str[i] = str[j];
- str[j] = temp;
- }
-
- for (int i = pattern.length - 1,j ++) {
- char temp = pattern[i];
- pattern[i] = pattern[j];
- pattern[j] = temp;
- }
- // 反转后
- try {
- for (int i = 0;i < pattern.length;i ++) {
- if (pattern[i] == '*') {
- if (pattern[i + 1] == '.')
- return true;
- char c = pattern[i + 1];
- int t2 = i + 2;
- int save2 = 0;
- while (t2 < pattern.length) {
- if (pattern[t2] == '*') {
- t2 += 2;
- } else if (pattern[t2] == c || pattern[t2] == '.') {
- while (t2 < pattern.length && (pattern[t2] == c || pattern[t2] == '.')) {
- save2 ++;
- t2 ++;
- }
- break;
- } else
- break;
- }
- int p = 0;
- for (char temp : str) {
- if (temp == c)
- p ++;
- else
- break;
- }
- if (p >= save2)
- p -= save2;
-
- // 构造新数组
- char[] newArray = new char[str.length - p];
- int k = 0;
- while (p < str.length) {
- newArray[k ++] = str[p ++];
- }
- str = newArray;
- // 跳过一个字符串
- i ++;
- } else if (pattern[i] == '.') {
- char[] newArray = new char[str.length - 1];
- int p = 0;
- for (int j = 1;j < str.length;j ++) {
- newArray[p] = str[j];
- }
- str = newArray;
- } else {
- if (pattern[i] == str[0]) {
- char[] newArray = new char[str.length - 1];
- int p = 0;
- for (int j = 1;j < str.length;j ++) {
- newArray[p ++] = str[j];
- }
- str = newArray;
- } else
- return false;
- }
- }
- } catch (Exception ex) {
- return false;
- }
- if (str.length != 0)
- return false;
- return true;
- }