package 牛客网剑指offer题库;public class 正则表达式匹配 {public static void main(String[] args
package 牛客网剑指offer题库; public class 正则表达式匹配 { public static void main(String[] args) { // TODO Auto-generated method stub 正则表达式匹配 test=new 正则表达式匹配(); System.out.println(test.match("".toCharArray(),".".toCharArray())); } public boolean match(char[] str, char[] pattern){ if(str.length==0&&pattern.length==0)return true; else return match1(str,pattern,0,0); } /** * si,pi表示当前函数要匹配的字符和对应的正则字符 * 首先，如果当前字符和正则字符同时走完，则返回true * 如果正则字符走完而匹配字符未走完，返回false * 如果正在字符未走完，匹配字符已走完，由于'*'的存在,继续匹配，比如ab,abc* * 匹配时分为下一个正则字符是*和不是* * 如果下一个正则字符存在且是*,那么如果当前字符存在且匹配，则可以选择不匹配当前字符和匹配当前字符，并用当前正则字符匹配下一个字符 * 如果当前字符不存在或不匹配，则选择不匹配当前字符 * 如果下一个不是*，那么如果当前字符存在且匹配，则继续匹配，否则返回false * @param str * @param pattern * @param si * @param pi * @return */ private boolean match1(char[] str, char[] pattern, int si, int pi) { // TODO Auto-generated method stub if(si>=str.length&&pi>=pattern.length) return true; if(pi>=pattern.length&&si<str.length) return false; if((pi+1)<pattern.length&& pattern[pi+1]=='*') { //如果当前字符匹配，尝试匹配完成或继续匹配 if(si<str.length&& (pattern[pi]=='.'||pattern[pi]==str[si])) { return match1(str, pattern, si, pi+2) ||match1(str,pattern,si+1,pi); }else return match1(str, pattern, si, pi+2); }else { if(si<str.length&& (pattern[pi]=='.'||pattern[pi]==str[si])) return match1(str, pattern,si+1,pi+1); else return false; } } }
