Leetcode题解:一道”难“题

原题地址:Problem 1332

       题目很直(mo)白(hu),就是从一个字符串中删除回文子列直到字符串为空。但是我——没看示例,盯着题目描述和左上角的“简单”,陷入了长时间的思考,最终怀疑人生。毕竟如果你要找回文串的话就得遍历一遍得到子串,然后删除,再遍历,再循环……如此反复,时间复杂度很高,完全不是简单难度,毫无办法的我最终只能看向题解,然后在惊叹中一分钟提交了答案。

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

       总之这道题很沙雕,沙雕之处就在于它的子序列可以不连续。所以,如果不是空串或者回文串的话,先删掉所有的 $a$ 再删掉所有的 $b$ 就行了。由于让我卡了很久,专门写了一篇博客,特此留念。