正则表达式匹配(java实现)

问题描述

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

解决方案

递归解决，代码如下：

public boolean match(char[] str, char[] pattern) { return match(str,0,pattern,0); } public boolean match(char[] str,int left1,char[] pattern,int left2){ if(str == null && pattern == null) return true; if(str.length == left1 && pattern.length == left2) return true; boolean FirstMatch = false; if(left1 < str.length && left2 < pattern.length && (pattern[left2] == '.' || str[left1] == pattern[left2])) FirstMatch = true; if(left2 < pattern.length - 1 && pattern[left2 + 1] == '*'){ if(FirstMatch){ return match(str,left1,pattern,left2 + 2) || match(str,left1 + 1,pattern,left2); } else return match(str,left1,pattern,left2 + 2); } else return FirstMatch && match(str,left1 + 1,pattern,left2 + 1); }