当前位置：首页 > article >正文

(暴力枚举水题长度为3的不同回文子序列）leetcode 1930

article 2025/3/20 7:54:33

关键就是去重，暴力没啥好说明的

class Solution {
public:
  
    int countPalindromicSubsequence(string s) {
        int ans = 0;
        int n = s.size();
        for (char i = 'a';i <= 'z';i++)//穷尽所有字母
        {
            int l= 0;
            int r = n - 1;
            while (l < n && s[l] != i)//找到左边第一个等于s[i]的下标
            {
                l++;
            }
            while (r > 0 && s[r] != i)//找到右边边第一个等于s[i]的下标
            {
                r--;
            }
            if (l >= r)//没找到跳过
            {
                continue;
            }
            //计算回文范围内不重复的字母数量 因为 在"bbcbaba"中，当i枚举到b则l=0，r=5,bbb与bbb算同一个子序列所以，在l和r去重后统计其中的字母数量
            //这里直接把l和r期间的值放入unordered_set在返回长度即可
            unordered_set<int>setf;
            for (int k = l + 1;k < r;k++)
                setf.insert(s[k]);
            ans += setf.size();




        }
        return ans;
    }
};

查看全文

http://www.kler.cn/a/592286.html