字符串中的匹配之递归

字符串的括号匹配是一个很常见的问题。用栈这种后进先出的结构是非常适合的。此外,字符串中的回文以及衍生的各种问题也是字符串处理中非常常见的。

今天再说一下这类相似的问题,如何用递归来转化成子结构来求解。

先放一条LeetCode例题: 680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: “aba”
Output: True

Example 2:
Input: “abca”
Output: True

题目的意思是:至多删除一个字母判断是否能删成回文。字符串长度是50000.

显然不能O(n\^2)暴力。然后我们分析一下,其实我们只要能找出这个有问题的字母的位置在哪里就好了,然后删掉它就行了。可以通过判断是哪个字母的个数是奇数来做吗?不能,因为判断出来是什么字母,但当这个字母有很多时我们还是不知道删掉其中的哪一个。

所以就用到所说的递归:

两个指针从左边和右分别扫,扫到不匹配的时候就递归,分别删掉左边或右边来判断其子串是不是回文。

注意的是,已经判断回文的部分就不需要递归了,否则就起不到递归的作用了。时间复杂度: O(n)

AC代码:

再放一道LeetCode例题: 678. Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

  1. Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
  2. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
  3. Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
  4. ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
  5. An empty string is also valid.

Example 1:
Input: "()"
Output: True

Example 2:
Input: "(*)"
Output: True

Example 3:
Input: "(*))"
Output: True

题意就是判断是否括号匹配,其中*可任意充当(或者)或者空白。

如果是没有*,那么做法很显然:从左到右统计(和)的个数。如果)的个数>(的个数就不行。判断到结尾的时候,如果两者个数相等就可以。

现在引入了*这个百搭,我们同样可以用递归来做:

如果遇到一个*,就分别把它视为(,)或者空白来递归。

AC代码:

另外,这道题再说一个很巧妙的做法,思路来源于讨论区的高票帖。

low代表左括号可能出现的下界,high代表左括号可能出现的上界。

  • 当遇到一个(时,low++,high++;
  • 当遇到一个)时,low–,high–;
  • 当遇到一个*时,low–,high++; (即我们既可以把*看成(也可以看成)
  • 注意的是,下界一旦小于0直接返回false代表右括号太多了,
    但是上界我们得人为保证其值>=0,因为可以伸缩(例如”(******”),但是最后结束的时候必须保证上界为0,否则就是左括号太多了。

代码:

点赞

发表评论

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