每日一题(2022-01-22):删除回文子序列

每日一题(2022-01-22):删除回文子序列

来源:力扣
难度:简单
题目:1332. 删除回文子序列

题目详情

原题截图.png

题解思路

搁这儿脑筋急转弯是吧……
构思了1w种解题思路,感觉是简单题目不应该这样做,看了题解回头读题才意识到对于“子序列”的定义竟然这么奇葩,也就是说:

  • 相同字符组成的子序列一定是回文子序列;
  • 如果字符串本身为回文序列,只需要删除1次就行;
  • 由于字符串仅由ab两种字符构成,所以可以先删除所有的a,再删除所有的b,最多仅需要删除两次;

代码结果

class Solution {
public:
    int removePalindromeSub(string s) {
        string s_cpy = s;
        reverse(s_cpy.begin(), s_cpy.end());
        return s == s_cpy ? 1 : 2;
    }
};

运行结果.png