GVKun编程网logo

leetcode 10. Regular Expression Matching

12

想了解leetcode10.RegularExpressionMatching的新动态吗？本文将为您提供详细的信息，此外，我们还将为您介绍关于*LeetCode10RegularExpressionM

想了解leetcode 10. Regular Expression Matching的新动态吗？本文将为您提供详细的信息，此外，我们还将为您介绍关于*LeetCode 10 Regular Expression Matching 正则表达式、LeetCode - Hard - 10. Regular Expression Matching、LeetCode -- Regular Expression Matching、LeetCode -- Regular Expression Matching 【算法】的新知识。

本文目录一览：

leetcode 10. Regular Expression Matching

leetcode 10. 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 = "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

经典的 DP 题。很难理解，详情请见印度三哥的白板详解

https://www.youtube.com/watch?v=l3hda49XcDE&index=17&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr

大致思路如下：

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == ''.'' : dp[i][j] = dp[i-1][j-1]; 3, If p.charAt(j) == ''*'': here are two sub conditions:  1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty  2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == ''.'':  dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a  or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a  or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
public boolean isMatch(String s, String p) {

    if (s == null || p == null) {
        return false;
    }
    boolean[][] dp = new boolean[s.length()+1][p.length()+1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == ''*'' && dp[0][i-1]) {
            dp[0][i+1] = true;
        }
    }
    for (int i = 0 ; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == ''.'') {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == s.charAt(i)) {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == ''*'') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != ''.'') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                } else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

 

*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的讲解已经结束，谢谢您的阅读，如果想了解更多关于*LeetCode 10 Regular Expression Matching 正则表达式、LeetCode - Hard - 10. Regular Expression Matching、LeetCode -- Regular Expression Matching、LeetCode -- Regular Expression Matching 【算法】的相关知识，请在本站搜索。

本文标签：

上一篇Docker 最全教程 —— 数据库容器化之持久保存数据（十一）（docker 存储持久化）

下一篇docker 私有仓库 yum 安装 docker-registry（docker私有仓库部署）

相关文章