X

LEETCODE 1332. Remove Palindromic Subsequences 解题思路分析

题目大意:

删除回文子序列

给你一个字符串 s,它仅由字母 ‘a’ 和 ‘b’ 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符(字符串为空)的最小删除次数。

「子序列」定义:如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到,那么这个字符串就是原字符串的一个子序列。

「回文」定义:如果一个字符串向后和向前读是一致的,那么这个字符串就是一个回文。

示例 1:

输入:s = "ababa"
输出:1
解释:字符串本身就是回文序列,只需要删除一次。

示例 2:

输入:s = "abb"
输出:2
解释:"abb" -> "bb" -> "". 
先删除回文子序列 "a",然后再删除 "bb"。

示例 3:

输入:s = "baabb"
输出:2
解释:"baabb" -> "b" -> "". 
先删除回文子序列 "baab",然后再删除 "b"。

示例 4:

输入:s = ""
输出:0

提示:

  • 0 <= s.length <= 1000
  • s 仅包含字母 ‘a’  和 ‘b’

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1332

解题思路分析:

这道题一开始想复杂了,我以为要使用动态规划来解题,后来仔细看了题目才发现,原来每一次可以删除一个回文子序列,而不是子串,这个信息很关键,如果每次可以删除子序列的话,理论上最多2次就可以删除完毕,我们可以先把所有a删除,再把所有b删除。

因此本题我们只需要判断给定的字符串是否是回文,如果是,1次可删除。若不是,需要删除2次。另外,如果字符串为空,则不需要删除,直接返回0。

实现代码:

public int removePalindromeSub(String s) {
    // 如果长度为0,返回0
    if(s.length()==0) return 0;
    // 定义双指针,分别指向字符串首尾位置
    int l=0,r=s.length()-1;
    // 由外向内判断字符串是否为回文
    while(l<=r){
       // 若当前两个字符不相同,说明不是回文,返回2
       if(s.charAt(l)!=s.charAt(r)){
           return 2;
       }
       // 将左右指针分别向内移动一位
       l++;
       r--;
    }
    // 如果是回文,返回1
    return 1;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Palindromic Subsequences.

Memory Usage: 37.2 MB, less than 100.00% of Java online submissions for Remove Palindromic Subsequences.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1332-remove-palindromic-subsequences-解题思路分析/
Categories: leetcode
kwantong: