正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 

在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

解法：

首先要想到用递归处理，如果不用递归，那就需要自己模拟栈的操作，很是复杂。

其次就是情况的具体分析了

关键是先列举测试用例

public class Solution {
	public static void main(String[] args) {
		Solution s = new Solution();
		// System.out.println(s.match("a".toCharArray(),".*".toCharArray()));
		// System.out.println(s.match("".toCharArray(),".".toCharArray()));
		// System.out.println(s.match("aa".toCharArray(),"a*".toCharArray()));
		// System.out.println(s.match("ab".toCharArray(),".*".toCharArray()));
		System.out.println(s.match("aaa".toCharArray(),"ab*ac*a".toCharArray()));
		System.out.println(s.match("bbbba".toCharArray(),".*a*a".toCharArray()));
		System.out.println(s.match("a".toCharArray(),".*".toCharArray()));

	}

	public boolean match(char[] str,char[] pattern) {
		return match(new String(str),new String(pattern));
	}

	public boolean match(String str,String pattern) {
		// Case 1
		// "",""
		if (str.length() == 0 && pattern.length() == 0)
			return true;

		// "",".*b*"
		if (str.length() == 0 && pattern.length() > 0) {
			// pattern.length == 1
			if (pattern.length() == 1)
				return false;

			// pattern.length > 1
			if (pattern.charAt(1) == '*')
				return match(str,pattern.substring(2));
			return false;
		}

		// "xxx",""
		if (pattern.length() == 0)
			return false;

		// Case2 str和pattern的长度都大于0时
		if (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.') {
			if (pattern.length() == 1)
				return match(str.substring(1),"");

			// pattern > 1
			if (pattern.charAt(1) != '*') {
				return match(str.substring(1),pattern.substring(1));

			} else if (pattern.charAt(1) == '*') {
				if (match(str.substring(1),pattern))
					return true;

				if (match(str,pattern.substring(2)))
					return true;

				if (match(str.substring(1),pattern.substring(2)))
					return true;
			}
		} else {
			if (pattern.length() == 1)
				return false;

			// pattern > 1
			if (pattern.charAt(1) == '*')
				return match(str,pattern.substring(2));
		}
		return false;
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!