GVKun编程网logo

【LeetCode】10. Regular Expression Matching（C++）（leetcode c++ pdf）

10

本文将介绍【LeetCode】10.RegularExpressionMatching的详细情况，特别是关于C++的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也

本文将介绍【LeetCode】10. Regular Expression Matching的详细情况，特别是关于C++的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于*LeetCode 10 Regular Expression Matching 正则表达式、LeetCode - Hard - 10. Regular Expression Matching、LeetCode -- Regular Expression Matching、LeetCode -- Regular Expression Matching 【算法】的知识。

本文目录一览：

【LeetCode】10. Regular Expression Matching（C++）（leetcode c++ pdf）

【LeetCode】10. Regular Expression Matching（C++）（leetcode c++ pdf）

地址：https://leetcode.com/problems/regular-expression-matching/

题目：

Given an input string (s) and a pattern (p),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).

Note:

s Could be empty and contains only lowercase letters a-z.

p Could be empty and contains only lowercase letters a-z,and characters like . or *.

Example 1:

Input: s = “aa” p = “a”

Output: false

Explanation: “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa” p = “a*”

Output: true

Explanation: ‘*’ means zero or more of the precedeng element,‘a’. Therefore,by repeating ‘a’ once,it becomes “aa”.

Example 3:

Input: s = “ab” p = “.*”

Output: true

Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:

Input: s = “aab” p = “cab”

Output: true

Explanation: c can be repeated 0 times,a can be repeated 1 time. Therefore it matches “aab”.

Example 5:

Input: s = “mississippi” p = “misisP*.”

Output: false

理解：

字符串的正则匹配，*可以匹配0个或多个字符，.可以匹配一个任意字符

思路是从头开始匹配，先看s[i]和p[j]是不是相同，或者p[j]=='.'，如果是，当前位置是匹配的。

‘*’如果有，必然出现在j+1的位置。

如果p[j+1]=='*'，需要判断两种情况。

s[i]开始的字符串和p[j+2]开始的字符串是否匹配，即*匹配了0个字符；

或者s[i]和p[j]是否相同，且s[i+1]和p[j]是否相同，即*匹配了一个字符。

否则，判断s[i]和p[j]是否相同，且s[i+1]和p[j+1]是否相同。

实现1：

最简单的递归实现，由于不停的复制string，效率很低

class Solution {

public:

bool isMatch(string s,string p) {

if (p.empty()) return s.empty();

bool first_match = (!s.empty() && (p.at(0) == s.at(0) || p.at(0) == '.'));

if (p.length() >= 2 && p.at(1) == '*') {

return isMatch(s,p.substr(2)) || (first_match && isMatch(s.substr(1),p));

}

else

return first_match&& isMatch(s.substr(1),p.substr(1));

}

};

实现2：

使用下标，代替了字符串复制

enum class Match {

FALSE,TRUE,UNKNowN

};

class Solution {

vector> result;

public:

bool isMatch(string s,string p) {

result = vector>(s.length() + 1,vector(p.length() + 1,Match::UNKNowN));

return dp(0,s,p);

}

bool dp(int i,int j,const string& s,const string& p) {

if (result[i][j] != Match::UNKNowN)

return result[i][j] == Match::TRUE;

bool res;

if (j == p.length())

res = (i == s.length());

else {

bool first_match = i < s.length() && (s.at(i) == p.at(j) || p.at(j) == '.');

if (j + 1 < p.length()&&p.at(j+1)=='*') {

res = dp(i,j + 2,p) || (first_match&&dp(i + 1,j,p));

}

else {

res = first_match&&dp(i + 1,j + 1,p);

}

}

result[i][j] = res ? Match::TRUE : Match::FALSE;

return res;

}

};

实现3：

上面的实现2，还是使用递归的方式，然而前面的位置是与后面的位置有关的，因此可以从后向前，记录后面的判断结果，避免递归调用

class Solution {

vector> dp;

public:

bool isMatch(string s,string p) {

dp = vector>(s.length() + 1,vector(p.length() + 1,false));

dp[s.length()][p.length()] = true;

for (int i = s.length(); i >= 0; --i)

for (int j = p.length() - 1; j >= 0; --j) {

bool first_match = i < s.length() && (s.at(i) == p.at(j) || p.at(j) == '.');

if (j + 1 < p.length() && p.at(j + 1) == '*') {

dp[i][j] = dp[i][j + 2] || (first_match &&dp[i + 1][j]);

}

else {

dp[i][j] = (first_match && dp[i + 1][j + 1]);

}

}

return dp[0][0];

}

};

*LeetCode 10 Regular Expression Matching 正则表达式

*LeetCode 10 Regular Expression Matching 正则表达式

题目：

https://leetcode.com/problems/regular-expression-matching/


思路：

（1）DFS

（2）自动机


DFS版本写的比较烂，然后很长逻辑混乱，基本就是出bug补上。。。

592ms

const int DEBUG = 0;

class Solution {
public:
    bool match(char a,char b) {
        return (a == b || b == '.');
    }
    bool isMatch(string s,string p) {
       if(dfs(s,p,0))
            return true;
        return false;
    }
    bool check(string p,int pos) {
        if( (p.size()-pos) %2 == 0 ){
            for(int i=1+pos; i<p.size(); i+=2)
                if(p[i] != '*')return false;
            return true;
        }
        return false;
    }

    bool dfs(string s,string p,int pos) {
        if(s.size() == 0) {
            /*if( (pos == p.size()&&p[pos-1]!='*' ||
                 (pos == p.size()-1 && p[pos]=='*'))
               )return true;*/
            if( (pos == p.size()&&p[pos-1]!='*' ||
                 (check(p,pos+1) && p[pos]=='*'))
               )return true;
            //if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;
            if(check(p,pos))return true;
            if(DEBUG) {
                cout << "s.size() == 0 s=" << s << "  p=" << p << "  pos=" << pos << endl;
            }
            return false;
        }
        if(p.size() <= pos) {
            if(DEBUG) {
                cout << "p.size() <= pos s=" << s << "  p=" << p << "  pos=" << pos << endl;
            }
            return false;
        }
        int ptrs = 0,ptrp = pos;
        while(ptrs < s.size() && ptrp < p.size() ) {
            if( match(s[ptrs],p[ptrp]) ) {
                if(ptrp+2 < p.size() && p[ptrp+1] == '*') {
                    if(dfs(s.substr(ptrs),ptrp+2))return true;
                }
                ptrs ++,ptrp ++;
                continue;
            }
            if(p[ptrp] == '*') {
                if(ptrp >= 1) {
                    if( match(s[ptrs],p[ptrp-1]) ) {
                        return dfs(s.substr(ptrs+1),ptrp) | dfs(s.substr(ptrs),ptrp+1);
                        //   | 1 | 0
                    } else {
                        return dfs(s.substr(ptrs),ptrp+1);
                    }
                } else {
                    return false;
                }
                continue;
            } //else {
            if(ptrp+1 < p.size() && p[ptrp+1] == '*'){
                    //cout << "s=" << s.substr(ptrs) << "  p=" << p << "  " << ptrp+2 << endl;
                return dfs(s.substr(ptrs),ptrp+2);
            }
            else
                return false;
            //}
        }
        if( ptrs >= s.size()  ){
            pos = ptrp;
            //if( (pos == p.size()&&p[pos-1]!='*') || (pos == p.size()-1 && p[pos]=='*') )return true;
            //if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;

            if( (pos == p.size()&&p[pos-1]!='*' ||
                 (check(p,pos+1) && p[pos]=='*'))
               )return true;
            if(check(p,pos))return true;
            return false;

        }
        //if(ptrp >= p.size())return false;
        return false;
    }
};


正则表达式写法：很优雅，但是时间692ms，应该是因为某些可以用循环，但是这里还是递归了


class Solution {
public:
    bool isMatch(string s,string p) {
        return matchHere(s,p);
    }
    bool matchHere(string s,string p) {
        if(s.size() == 0) {
            return p.size()==0 || p.size()%2==0&&p[1]=='*'&&matchStar('\0',s,p.substr(2));
        }
        if(p.size() >=2 && p[1]=='*' && matchStar(p[0],p.substr(2)))
            return true;
        if(s[0] == p[0] || p[0] == '.') {
            return matchHere(s.substr(1),p.substr(1));
        }
        return false;
    }
    //c* and p has erased c*
    bool matchStar(char c,string s,string p){
        int ptr = -1;
        do {
            ++ptr;
            if(matchHere(s.substr(ptr),p))return true;
        } while( ptr<s.size() && ( s[ptr]==c || c=='.' ) );
        return false;
    }
};


正则表达式的写法参考：

http://hexlee.iteye.com/blog/552361

里面有^和&的处理方法

有空再去练习下怎么DFS写得优雅，比如http://blog.csdn.net/doc_sgl/article/details/12719761

LeetCode - Hard - 10. Regular Expression Matching

LeetCode - Hard - 10. Regular Expression Matching

Topic

  • String
  • Dynamic Programming
  • Backtracking

Description

https://leetcode.com/problems/regular-expression-matching/

Given an input string (s) and a pattern (p), implement regular expression matching with support for ''.'' and ''*'' where:

  • ''.'' Matches any single character.
  • ''*'' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: ''*'' means zero or more of the preceding element, ''a''. Therefore, by repeating ''a'' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Constraints:

  • 0 <= s.length <= 20
  • 0 <= p.length <= 30
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, ''.'', and ''*''.
  • It is guaranteed for each appearance of the character ''*'', there will be a previous valid character to match.

Analysis

方法一：动态规划

Consider following example

s=''aab'', p=''c*a*b''

      c * a * b
    0 1 2 3 4 5
  0 y
a 1
a 2
b 3

dp[i][j] denotes if s.substring(0,i) is valid for pattern p.substring(0,j). For example dp[0][0] == true (denoted by y in the matrix) because when s and p are both empty they match. So if we somehow base dp[i+1][j+1] on previos dp[i][j]''s then the result will be dp[s.length()][p.length()]

So what about the first column? for and empty pattern p="" only thing that is valid is an empty string s="" and that is already our dp[0][0] which is true. That means rest of dp[i][0] is false.

s=''aab'', p=''c*a*b''

      c * a * b
    0 1 2 3 4 5
  0 y
a 1 n
a 2 n
b 3 n

What about the first row? In other words which pattern p matches empty string s=""? The answer is either an empty pattern p="" or a pattern that can represent an empty string such as p="a*", p="z*" or more interestingly a combiation of them as in p="a*b*c*". Below for loop is used to populate dp[0][j]. Note how it uses previous states by checking dp[0][j-2]

for (int j=2; j<=p.length(); j++) {
	dp[0][j] = p.charAt(j-1) == ''*'' && dp[0][j-2];
}

At this stage our matrix has become as follows: Notice dp[0][2] and dp[0][4] are both true because p="c*" and p="c*a*" can both match an empty string.

s=''aab'', p=''c*a*b''

      c * a * b
    0 1 2 3 4 5
  0 y n y n y n
a 1 n
a 2 n
b 3 n

So now we can start our main iteration. It is basically the same, we will iterate all possible s lengths (i) for all possible p lengths (j) and we will try to find a relation based on previous results. Turns out there are two cases.

  1. (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == ''.'') if the current characters match or pattern has . then the result is determined by the previous state dp[i][j] = dp[i-1][j-1]. Don''t be confused by the charAt(j-1) charAt(i-1) indexes using a -1 offset that is because our dp array is actually one index bigger than our string and pattern lenghts to hold the initial state dp[0][0].

  2. if p.charAt(j-1) == ''*'' then either it acts as an empty set and the result is dp[i][j] = dp[i][j-2] or (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == ''.'') current char of string equals the char preceding * in pattern so the result is dp[i-1][j].

So here is the final state of matrix after we evaluate all elements:

s=''aab'', p=''c*a*b''

      c * a * b
    0 1 2 3 4 5
  0 y n y n y n
a 1 n n n y y n
a 2 n n n n y n
b 3 n n n n n y

Time and space complexity are O(p.length() * s.length()).

Try to evaluate the matrix by yourself if it is still confusing,

方法二：递归

There are two cases to consider:

First, the second character of p is *, now p string can match any number of character before *. if(isMatch(s, p.substring(2)) means we can match the remaining s string, otherwise, we check if the first character matches or not.

Second, if the second character is not *, we need match character one by one.

Submission

public class RegularExpressionMatching {
	//方法一：动态规划
	public boolean isMatch1(String s, String p) {
		if (p == null || p.length() == 0)
			return (s == null || s.length() == 0);

		boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
		dp[0][0] = true;
		for (int j = 2; j <= p.length(); j++) {
			dp[0][j] = p.charAt(j - 1) == ''*'' && dp[0][j - 2];
		}

		for (int j = 1; j <= p.length(); j++) {
			for (int i = 1; i <= s.length(); i++) {
				if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == ''.'')
					dp[i][j] = dp[i - 1][j - 1];
				else if (p.charAt(j - 1) == ''*'')
					dp[i][j] = dp[i][j - 2]
							|| ((s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == ''.'') && dp[i - 1][j]);
			}
		}

		return dp[s.length()][p.length()];
	}

	//方法二：递归
	public boolean isMatch2(String s, String p) {
		if (p.length() == 0) {
			return s.length() == 0;
		}
		if (p.length() > 1 && p.charAt(1) == ''*'') { // second char is ''*''
			if (isMatch2(s, p.substring(2))) {
				return true;
			}
			if (s.length() > 0 && (p.charAt(0) == ''.'' || s.charAt(0) == p.charAt(0))) {
				return isMatch2(s.substring(1), p);
			}
			return false;
		} else { // second char is not ''*''
			if (s.length() > 0 && (p.charAt(0) == ''.'' || s.charAt(0) == p.charAt(0))) {
				return isMatch2(s.substring(1), p.substring(1));
			}
			return false;
		}
	}

}

Test

import static org.junit.Assert.*;
import org.junit.Test;

public class RegularExpressionMatchingTest {

	@Test
	public void test() {
		RegularExpressionMatching obj = new RegularExpressionMatching();

		assertFalse(obj.isMatch1("aa", "a"));
		assertTrue(obj.isMatch1("aa", "a*"));
		assertTrue(obj.isMatch1("ab", ".*"));
		assertTrue(obj.isMatch1("aab", "c*a*b"));
		assertFalse(obj.isMatch1("mississippi", "mis*is*p*."));
		
		assertFalse(obj.isMatch2("aa", "a"));
		assertTrue(obj.isMatch2("aa", "a*"));
		assertTrue(obj.isMatch2("ab", ".*"));
		assertTrue(obj.isMatch2("aab", "c*a*b"));
		assertFalse(obj.isMatch2("mississippi", "mis*is*p*."));
		
	}
}

LeetCode -- Regular Expression Matching

LeetCode -- Regular Expression Matching

正则表达式匹配：

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

'.' 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
class Solution {
public:
    bool isMatch(const char *s,const char *p) {
        if(p[0] == '\0') return s[0] == '\0';
        if(p[0] == '*')  return isMatch(s,p + 1);
        if(p[1] == '*'){
            if(s[0] == '\0') return isMatch(s,p + 2);
            if(p[0] == '.')  return isMatch(s + 1,p) || isMatch(s,p + 2);
            return (s[0] == p[0] && isMatch(s + 1,p)) || isMatch(s,p + 2);
        } else {
            if(p[0] == '.')  return s[0] != '\0' && isMatch(s + 1,p + 1);
            return s[0] == p[0] && isMatch(s + 1,p + 1);
        }
    }
};

LeetCode -- Regular Expression Matching 【算法】

LeetCode -- Regular Expression Matching 【算法】

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
题目要求实现一个可以支持'.'和'*'的正则表示，代码如下：



依题意，我们根据字符串P的下一个字符是否是'*'来分开讨论(见代码第7行)。如果是，那么必须在两字符串当前位置进行比较；否则，让字符串P的当前位置与字符串S的当前及后面各位比较直至不匹配，并开始下一轮的比较。为了避免字符串P的'*'匹配过多的项，还要对S从当前位置开始的子串和P从当前位置后面两位开始的子串进行匹配(样例：a ab* )。

我们今天的关于【LeetCode】10. Regular Expression Matching和C++的分享就到这里，谢谢您的阅读，如果想了解更多关于*LeetCode 10 Regular Expression Matching 正则表达式、LeetCode - Hard - 10. Regular Expression Matching、LeetCode -- Regular Expression Matching、LeetCode -- Regular Expression Matching 【算法】的相关信息，可以在本站进行搜索。

本文标签：

上一篇表格隔行换色 css expression（表格隔行换色）

下一篇关于SQL中CTE（公用表表达式）（Common Table Expression）的总结

相关文章