Skip to main content

[leetcode]第三部分

1-Regular Expression Matching

问题描述

给定一个输入字符串s和一个模式p,实现一个支持'.''*'的正则匹配:

  • '.'匹配任何单个字符
  • '*'匹配'0'或多个之前的元素

匹配应该覆盖完整的输入字符串(而不是部分的)。

注意
s是空字符串或者只包含小写字符a-z的字符串
p是空字符串或者是包含小写字符a-z以及像.*的字符的字符串

示例一
输入:
s = "aa"
p = "a"
输出:false
解释:"a" 无法匹配完整的字符串"aa"
------
示例二
输入:
s = "aa"
p = "a*"
输出:true
解释:'*' 表示0个或多个之前的元素'a' ,因此通过重复 'a' 一次,字符串变成了 'aa'。
------
示例三
输入:
s = "ab"
p = ".*"
输出:true
解释:".*" 表示 "0个或多个(*) 任意字符(.)"。
------
示例四
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: c 重复 0 次, a 重复 1 次。 一次可以匹配 "aab"。
------
示例五
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解题思路

如果没有*的话,可以直接从前到后进行匹配,遇到不相等的符号就直接返回;但是,如果有*的话,就得考虑匹配有0个或者多个(两种情况有一种满足即可)。

在这里,我们考虑用递归的方法进行解决(具体代码见方案一)。

第二种方案考虑使用动态规划来求解,状态定义为d[i,j]表示s[i:]p[j:]是否匹配,状态转移方程定义如下:

d[i,j]=\begin{cases} d[i+1,j+1] \land s[i] == p[j] & \text{if p[j+1]!=’*’, i>1, j >1} \\ d[i,j+2] \lor d[i+1,j] & \text{if p[j+1]==’*’} \end{cases}

初始化:
d[-1,-1] = True

具体代码见方案二

代码

方案一

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if not p:
            return not s
        firstMatch = bool(s) and p[0] in {s[0], '.'}
        if len(p) >= 2 and p[1] == '*':
            # repeat 0 time or repeat 1+ time
            return self.isMatch(s, p[2:]) or (firstMatch and self.isMatch(s[1:], p))
        else:
            # continue to match
            return firstMatch and self.isMatch(s[1:], p[1:])

方案二

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m = len(s)
        n = len(p)
        d = [[False] * (n+1) for i in range(m+1)]
        d[-1][-1]= True
        for i in range(m, -1, -1):
            for j in range(n-1, -1, -1):
                firstMatch = i < m and p[j] in {s[i], '.'}
                if j+1 < n and p[j+1] == '*':
                    d[i][j] = d[i][j+2] or (firstMatch and d[i+1][j])
                else:
                    d[i][j] = firstMatch and d[i+1][j+1]
        return d[0][0]

2-Container With Most Water

问题描述

给定n个非负整数a_1, a_2, .., a_n,分别表示坐标(i,a_i)上的点,绘制n条垂直的线,使得第i条线的两个顶点分别是(i, a_i)(i, 0)。找到两条线,与x轴一起,形成一个容器,使得容器包含最多的水量。

注意:不可以倾斜容器,n最小为2

解决思路

先通过画图来了解下题目的意思,是希望计算[i,0],[i,a_i],[j,0],[j,a_j]四点构成容器的存水量:

Alt text

假设找到两点(i,j),使得容器储水量最多,那么容量计算如下:

s=|j-i|*min(a_i,a_j)

得到这个公式,很容易就想到一个最简单的方式,两层遍历,一定能得到一个最大值。此时,时间算法复杂度为o(n^2),其中n为数组的长度。但是,很遗憾,这种方法没有被AC,因为有的例子超过了时间的限制。

得想办法降低计算复杂度

打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注