Skip to content

Latest commit

 

History

History
134 lines (92 loc) · 3.72 KB

2019-06-09.md

File metadata and controls

134 lines (92 loc) · 3.72 KB
Raw

每日一题 - 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

本题要求判断给出的字符串和对应的正则是否匹配，匹配返回true，否则返回false。

本题光从解题来看，可以使用api作弊，比如用Java字符串的matches方法就可以一步过这道题，本题老老实实做的话，就需要用到动态规划。基本思路是考察s和p任意从头到两个字符之间的匹配程度，有点像编辑距离那道题。

参考答案

class Solution {
    public boolean isMatch(String s, String p) {
      if (s == null || p == null) return false;
 
      // dp[i][j]代表s的前i位字符和p的前j位字符的匹配程度
      // dp[1][2]代表s的第一个字符和p的前两个字符的匹配
      // 如果s的第i个字符和p的第j个相等或者j为.那么di[i][j]的匹配程度取决于dp[i - 1][j - 1]
      // 如果p的第j个字符为*，那么就要考虑*匹配0个，1个，n个s的第i个字符的情况，以及根本匹配不了的情况
      // 根本匹配不了的意思是指p的j - 1个字符和s的第i个字符不相同，此时的匹配情况是dp[i][j] = dp[i][j - 2]
      // 然后是p的第j - 1个字符是.或者和s的i个字符相同的情况，此时可以匹配0 1 个n个s的第i个字符
      // 0个: dp[i][j] = dp[i][j - 2]
      // 1个: dp[i][j] = dp[i - 1][j - 1]
      // n个: dp[i][j] = dp[i - 1][j]
      // n个的最不好理解，可以按照下面的想
      // 我能匹配你n个，我肯定匹配了你前面的n-1个，也就是dp[i - 1][j]
      // 最后的结果是dp[s.length()][p.length()]
      boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];

      dp[0][0] = true;

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

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

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

其他优秀解答

暂无