Question

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

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 (.)".

Constraints:

1 <= s.length <= 20
1 <= p.length <= 20
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.

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="a*b", and directly enter the while loop Later, we find that “ab” and “b” do not match, so s becomes “

Code

/*
 * 1. two cases, "*" is 0 or non-0:
 * 		1.1: cccbbbaaa matching c*b*a*
 * 		1.2: bbbaaa matching c*b*a*
 *
 */

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));
	    }
	}
}

############

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (i > 0 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
                        f[i][j] |= f[i - 1][j];
                    }
                } else if (i > 0
                    && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[m][n];
    }
}

// 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:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i][j - 2]
                    if i > 0 and (p[j - 2] == "." or s[i - 1] == p[j - 2]):
                        f[i][j] |= f[i - 1][j]
                elif i > 0 and (p[j - 1] == "." or s[i - 1] == p[j - 1]):
                    f[i][j] = f[i - 1][j - 1]
        return f[m][n]

############

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]

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	f := make([][]bool, m+1)
	for i := range f {
		f[i] = make([]bool, n+1)
	}
	f[0][0] = true
	for i := 0; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				f[i][j] = f[i][j-2]
				if i > 0 && (p[j-2] == '.' || p[j-2] == s[i-1]) {
					f[i][j] = f[i][j] || f[i-1][j]
				}
			} else if i > 0 && (p[j-1] == '.' || p[j-1] == s[i-1]) {
				f[i][j] = f[i-1][j-1]
			}
		}
	}
	return f[m][n]
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const m = s.length;
    const n = p.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    f[0][0] = true;
    for (let i = 0; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i][j - 2];
                if (i && (p[j - 2] === '.' || p[j - 2] == s[i - 1])) {
                    f[i][j] |= f[i - 1][j];
                }
            } else if (i && (p[j - 1] === '.' || p[j - 1] == s[i - 1])) {
                f[i][j] = f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
};

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] f = new bool[m + 1, n + 1];
        f[0, 0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i, j] = f[i, j - 2];
                    if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
                        f[i, j] |= f[i - 1, j];
                    }
                } else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
                    f[i, j] = f[i - 1, j - 1];
                }
            }
        }
        return f[m, n];
    }
}

10 - Regular Expression Matching

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions