1332. 删除回文子序列

English Version

题目描述

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= s.length <= 1000
• s 仅包含字母 'a'  和 'b'

解法

• 如果字符串 s 本身是个回文串，那么只需要删除 1 次。
• 如果字符串 s 不是个回文串，我们注意到 s 最多只有两种字母 "a", "b"，并且删除的是一个子序列，因此可以先删除所有字母 "a" ("aaa...aaa" 是个回文串)，再删除所有字母 "b"，即可使得字符串变为空。因此需要的删除次数是 2 次。

Python3

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        if s[::-1] == s:
            return 1
        return 2

Java

class Solution {
    public int removePalindromeSub(String s) {
        if (s.length() == 0) {
            return 0;
        }
        if (new StringBuilder(s).reverse().toString().equals(s)) {
            return 1;
        }
        return 2;
    }
}

TypeScript

function removePalindromeSub(s: string): number {
    if (s.length == 0) return 0;
    if (s == s.split('').reverse().join('')) return 1;
    return 2;
}

C++

class Solution {
public:
    int removePalindromeSub(string s) {
        if (s.empty())
            return 0;
        string t = s;
        reverse(s.begin(), s.end());
        if (s == t)
            return 1;
        return 2;
    }
};

Go

func removePalindromeSub(s string) int {
	if len(s) == 0 {
		return 0
	}
	if s == reverse(s) {
		return 1
	}
	return 2
}

func reverse(s string) string {
	r := []byte(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

Rust

impl Solution {
    pub fn remove_palindrome_sub(s: String) -> i32 {
        let mut l = 0;
        let mut r = s.len() - 1;
        let s: Vec<char> = s.chars().collect();
        while l < r {
            if s[l] != s[r] {
                return 2;
            }
            l += 1;
            r -= 1;
        }
        1
    }
}

...