LeetCode - Hard - 10. Regular Expression Matching

た 入场券 2022-11-19 15:51 138阅读 0赞

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:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

  1. Input: s = "mississippi", p = "mis*is*p*."
  2. 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

  1. s='aab', p='c*a*b'
  2. c * a * b
  3. 0 1 2 3 4 5
  4. 0 y
  5. a 1
  6. a 2
  7. 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.

  1. s='aab', p='c*a*b'
  2. c * a * b
  3. 0 1 2 3 4 5
  4. 0 y
  5. a 1 n
  6. a 2 n
  7. 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]

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

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.

  1. s='aab', p='c*a*b'
  2. c * a * b
  3. 0 1 2 3 4 5
  4. 0 y n y n y n
  5. a 1 n
  6. a 2 n
  7. 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. ifp.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:

  1. s='aab', p='c*a*b'
  2. c * a * b
  3. 0 1 2 3 4 5
  4. 0 y n y n y n
  5. a 1 n n n y y n
  6. a 2 n n n n y n
  7. 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

  1. public class RegularExpressionMatching {
  2. //方法一:动态规划
  3. public boolean isMatch1(String s, String p) {
  4. if (p == null || p.length() == 0)
  5. return (s == null || s.length() == 0);
  6. boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
  7. dp[0][0] = true;
  8. for (int j = 2; j <= p.length(); j++) {
  9. dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
  10. }
  11. for (int j = 1; j <= p.length(); j++) {
  12. for (int i = 1; i <= s.length(); i++) {
  13. if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.')
  14. dp[i][j] = dp[i - 1][j - 1];
  15. else if (p.charAt(j - 1) == '*')
  16. dp[i][j] = dp[i][j - 2]
  17. || ((s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
  18. }
  19. }
  20. return dp[s.length()][p.length()];
  21. }
  22. //方法二:递归
  23. public boolean isMatch2(String s, String p) {
  24. if (p.length() == 0) {
  25. return s.length() == 0;
  26. }
  27. if (p.length() > 1 && p.charAt(1) == '*') { // second char is '*'
  28. if (isMatch2(s, p.substring(2))) {
  29. return true;
  30. }
  31. if (s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0))) {
  32. return isMatch2(s.substring(1), p);
  33. }
  34. return false;
  35. } else { // second char is not '*'
  36. if (s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0))) {
  37. return isMatch2(s.substring(1), p.substring(1));
  38. }
  39. return false;
  40. }
  41. }
  42. }

Test

  1. import static org.junit.Assert.*;
  2. import org.junit.Test;
  3. public class RegularExpressionMatchingTest {
  4. @Test
  5. public void test() {
  6. RegularExpressionMatching obj = new RegularExpressionMatching();
  7. assertFalse(obj.isMatch1("aa", "a"));
  8. assertTrue(obj.isMatch1("aa", "a*"));
  9. assertTrue(obj.isMatch1("ab", ".*"));
  10. assertTrue(obj.isMatch1("aab", "c*a*b"));
  11. assertFalse(obj.isMatch1("mississippi", "mis*is*p*."));
  12. assertFalse(obj.isMatch2("aa", "a"));
  13. assertTrue(obj.isMatch2("aa", "a*"));
  14. assertTrue(obj.isMatch2("ab", ".*"));
  15. assertTrue(obj.isMatch2("aab", "c*a*b"));
  16. assertFalse(obj.isMatch2("mississippi", "mis*is*p*."));
  17. }
  18. }

发表评论

表情:
评论列表 (有 0 条评论,138人围观)

还没有评论,来说两句吧...

相关阅读