*[LeetCode] 10.Regular Expression Matching

本文主要是介绍*[LeetCode] 10.Regular Expression Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目原文

https://leetcode-cn.com/problems/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 entireinput 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".

  给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

  '.' 匹配任意单个字符。
  '*' 匹配零个或多个前面的元素。
  

  匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

  说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

  ---

  题目思路

这道题目可以考虑动态规划的方法。建立数字，使得DP[i][j]表示s中前i个字符与p的前j个字符组成的表示式是否匹配。

接下来，读取整个矩阵来进行判别。

---

程序代码

class Solution(object):def isMatch(self, s, p):""" :type s: str :type p: str :rtype: bool """#dp[i][j] 表示s中前i个字符与p的前j个字符组成的表示式是否匹配dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]dp[0][0] = Truefor i in range(len(dp)):print(dp[i])print('------------------------') for j in range(2,len(p) + 1):if p[j - 1] == '*':dp[0][j] = dp[0][j - 2]  for i in range(len(dp)):print(dp[i])    print('------------------------')    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][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))elif p[j-1] == '.' or s[i-1] == p[j - 1]:dp[i][j] = dp[i-1][j-1]for i in range(len(dp)):print(dp[i])return dp[len(s)][len(p)]

 

这篇关于*[LeetCode] 10.Regular Expression Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---