首页 > 代码库 > Regular Expression Matching

Regular Expression Matching

2024-09-16 10:31:36   222人阅读

题目

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

方法

使用递归的思想,分为两种情况：
1. p[i + 1] != ‘*‘, 返回 p[i] == s[j] && (s(j + 1), p(i + 1)):递归求解
2. p[i + 1] == ‘*‘,分p[i] != s[j], 递归求解（s(j), p(i + 2)）
     p[i] == s[j] 递归求解（s(j), p(i + 2)）以及 (s(j + 1) ,p (i + 2))
	private boolean getMatch(String s, int lenS, int curS, String p, int lenP, int curP) {
		
		if (curP == lenP) {
			return curS == lenS;
		}
		if (curP + 1 == lenP || p.charAt(curP + 1) != ‘*‘) {
			if (curS == lenS) {
				return false;
			}
			return (p.charAt(curP) == s.charAt(curS) || p.charAt(curP) == ‘.‘) && getMatch(s, lenS, curS + 1, p, lenP, curP + 1);
		}
		
		while (curS < lenS && (s.charAt(curS) == p.charAt(curP) || p.charAt(curP) == ‘.‘)) {
			if (getMatch(s, lenS, curS, p, lenP, curP + 2)) {
				return true;
			}
			curS++;
		}
		return getMatch(s, lenS, curS, p, lenP, curP + 2);
	}
    public boolean isMatch(String s, String p) {
    	if ((s == null && p == null) || (s.length() == 0 && p.length() == 0)) {
    		return true;
    	}
    	int lenS = s.length();
    	int lenP = p.length();
        return getMatch(s, lenS, 0, p, lenP, 0);
    }



Regular Expression Matching


联系
我们