Question

Formatted question description: https://leetcode.ca/all/10.html

10	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

@tag-dp

Algorithm

The general idea is as follows:

  • If p is empty, if s is also empty, return true, otherwise return false.

  • If the length of p is 1, if the length of s is also 1, and the same or p is’.’, it returns true, otherwise it returns false.

  • If the second character of p is not *, if s is empty at this time, false is returned, otherwise it is judged whether the first character matches, and the recursive function matching is called from the respective second character.

  • If the second character of p is *, perform the following loop. The condition is that if s is not empty and the first character matches (including p[0] as a dot), call the recursive function to match s and remove the first two characters of p( The reason for this is to assume that the role of the asterisk at this time is to make the preceding character appear 0 times to verify whether it matches), if the match returns true, otherwise the first letter of s is removed (because the first letter is matched at this time, we can remove the s Because of the asterisk, p can have any initials, so there is no need to remove them), and continue the loop.

  • Return the result of calling the recursive function to match s and remove the first two characters of p (the reason for this is to deal with the content that the asterisk cannot match, such as s=”ab”, p=”ab”, and directly enter the while loop Later, we find that “ab” and “b” do not match, so s becomes “b”, then after jumping out of the loop, we go to the last return to compare “b” and “b” and return true. An example, such as s=””, p=”a”, because s is empty, no if and while will be entered, and can only be compared at the last return and return true, correct).

/*

    1. two cases, “*” is 0 or non-0:
  • 1.1: cccbbbaaa matching cba*
  • 1.2: bbbaaa matching cba* * */

Code

Java

  • 
    public class Regular_Expression_Matching {
    
    	public static void main(String[] args) {
    		Regular_Expression_Matching out = new Regular_Expression_Matching();
    		Solution s = out.new Solution();
    
    		System.out.println(s.isMatch("aa", "a*"));
    
    		System.out.println(s.isMatch("aaa", "ab*a")); // false. same as: "aa","b*a"
    
    		System.out.println(s.isMatch("cccbbbaaa", "c*b*a*"));
    		System.out.println(s.isMatch("bbbaaa", "c*b*a*"));
    
    		Solution s2 = out.new Solution();
    		System.out.println(s2.isMatch("aaa", "ab*a")); // false. same as: "aa","b*a"
    
    	}
    
    
        public class Solution_iteration {
            public boolean isMatch(String s, String p) {
    
                int i = 0, j = 0, iStar = -1, jStar = -1, m = s.length(), n = p.length();
    
                while (i < m) {
                    if (j < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                        ++i;
                        ++j;
                    } else if (j < n && p.charAt(j) == '*') {
                        iStar = i;
                        jStar = j++;
                    } else if (iStar >= 0) {
                        i = ++iStar;
                        j = jStar + 1;
                    } else {
                        return false;
                    }
                }
    
                while (j < n && p.charAt(j) == '*') {
                    ++j;
                }
    
                return j == n;
            }
    	}
    
    	public class Solution {
    	    public boolean isMatch(String s, String p) {
    	        if(s == null || p == null) {
    	            return false;
    	        }
    
    	        if(p.length() == 0) {
    	            return s.length() == 0;
    	        }
    
    	        if(p.length() == 1) {
    	            // @note: if(p.charAt(0) == "*"), not possible, since * must be following a char, cannot match "aaaaa" with "*", but with "a*"
    	            return (s.length() == 1) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' || p.charAt(0) == '*');
    	        }
    
    	        // now p.length is at least 2
    	        if(p.charAt(1) != '*') { // @note: char is single quote... if(p.charAt(1) != "*") {
    	            if(s.length() == 0) {
    	                return false;
    	            } else {
    	                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
    	            }
    	        }
    
    	        // now 2nd char of p is "*"
    	        // case 1.1: cccbbbaaa matching c*b*a*
    	        int i = 0;
    	        // @note: 1. missed p.charAt(0) == '.'
    	        // @note: 2. order of conditions, first check if i is out of boundary, then check the rest
    	        // while(s.charAt(i) == p.charAt(0) && i < s.length()) {
    	        // while((s.charAt(i) == p.charAt(0) || p.charAt(0) == '.') && i < s.length()) {
    	        while(i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) { // "aa","b*a"
    	            // one match is enough
    	            if(isMatch(s.substring(i + 1), p.substring(2))) {
    	                return true;
    	            }
    
    	            i++;
    	        }
    
    	        // case 1.2: bbbaaa matching c*b*a*
    	        return isMatch(s, p.substring(2));
    	    }
    	}
    }
    
  • // OJ: https://leetcode.com/problems/regular-expression-matching/
    // Time: O(MN)
    // Space: O(M)
    class Solution {
    private:
        inline bool matchChar(string &s, int i, string &p, int j) {
            return p[j] == '.' ? i < s.size() : s[i] == p[j];
        }
        bool isMatch(string s, int i, string p, int j) {
            if (j == p.size()) return i == s.size();
            if (j + 1 < p.size() && p[j + 1] == '*') {
                bool ans = false;
                while (!(ans = isMatch(s, i, p, j + 2))
                && matchChar(s, i, p, j)) ++i;
                return ans;
            } else {
                return matchChar(s, i, p, j) && isMatch(s, i + 1, p, j + 1);
            }
        }
    public:
        bool isMatch(string s, string p) {
            return isMatch(s, 0, p, 0);
        }
    };
    
  • class Solution(object):
      def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True
        for j in range(1, len(p) + 1):
          if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
    
        for i in range(1, len(s) + 1):
          for j in range(1, len(p) + 1):
            if p[j - 1] != "*":
              dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == ".")
            else:
              dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == ".")
        return dp[-1][-1]
    
    

All Problems

All Solutions