Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

实现支持 ' . '和 ' * '的正則表達式。

' . ' 匹配不论什么单字符。

' * '匹配0或多个前向元素。

使用递归进行推断。

整体上能够分成两种情况，一种是以 ' * ‘开头的，还有一种不是。

public class RegularExpressionMatching {

	public static void main(String[] args) {

		System.out.println(isMatch("aa","a"));

		System.out.println(isMatch("aa","aa"));

		System.out.println(isMatch("aaa","aa"));

		System.out.println(isMatch("aa", "a*"));

		System.out.println(isMatch("aa", ".*"));

		System.out.println(isMatch("ab", ".*"));

		System.out.println(isMatch("aab", "c*a*b"));

	}

	public static boolean isMatch(String s,String p){

		if(p.length() == 0)

			return s.length() == 0;

		if(p.length() == 1 || p.charAt(1) != '*'){

			if(s.length()  < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))

				return false;

			return isMatch(s.substring(1),p.substring(1));

		}else{

			int i = -1;

			while(i < s.length() && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))){

				if(isMatch(s.substring(i+1),p.substring(2)))

					return true;

				i++;

			}

			return false;

		}

	}

}

Reference：http://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/