正则表达式匹配

2/22/2017来源:ASP.NET技巧人气:1836

题目描述

请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配

算法解析: 同时遍历两个字符串,当匹配模式串中的当前值不是’*‘,下一个值为’*‘的时候,而’*’表示它前面的字符可以出现任意次(包含0次),所以遇到这种情况的时候,这个模式字符可能出现0次,1次,或者多次,所以剩下字符串和模式串的匹配结果由这三种的结果共同影响。

代码如下:

public boolean match(char[] str, char[] pattern) { if (str == null || pattern == null){ return false; } return matchCore(str, pattern, 0, 0); } PRivate boolean matchCore(char[] str, char[] pattern, int i, int j) { if (i == str.length && j == pattern.length){ //适用于"", "" return true; } if (i == str.length && j != pattern.length){ //适用于"", ".*" while (j != pattern.length){ if(pattern[j] != '*' && (j + 1 >= pattern.length || pattern[j + 1] != '*')){ return false; } j++; } return true; } if (i != str.length && j == pattern.length){ //适用于"abc", "" return false; } if (j == pattern.length - 1){ if (str[i] == pattern[j] || pattern[j] == '.'){ return matchCore(str, pattern, i + 1, j + 1); } return false; } if (pattern[j + 1] == '*'){ if (pattern[j] == str[i] || (pattern[j] == '.' && i != str.length)){ return matchCore(str, pattern, i + 1, j + 2) || matchCore(str, pattern, i + 1, j) || matchCore(str, pattern, i, j + 2); }else{ return matchCore(str, pattern, i, j + 2); } } if (str[i] == pattern[j] || (pattern[j] == '.' && i != str.length)){ return matchCore(str,pattern, i + 1, j + 1); } return false; }