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

元音辅音字符串计数leetcode3305,3306

article 2025/3/17 13:51:49

题目链接：3305. 元音辅音字符串计数 I - 力扣（LeetCode）

思路一：暴力枚举

暴力枚举出所有子字符串，统计所有满足每个元音字母都出现及k个辅音字母的字符串个数

其中可以使用set集合判断子串中是否每个元音字母都出现，用一个变量count来统计辅音字母的出现次数。

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        set<char> vowels={'a','e','i','o','u'};
        int ret=0;
        for(int i=0;i<word.size();i++)
        {
            set<char> cur;
            int count=0;
            for(int j=i;j<word.size();j++)
            {
                if(vowels.count(word[j]))
                cur.insert(word[j]);
                else
                count++;

                if(vowels.size()==cur.size()&&count==k)
                ret++;
            }
        }
        return ret;
    }
};

该思路，只能通过第一题，第二题的数据范围大，会超时。

思路二：滑动窗口

暴力解法的思路，我们每次在用两个变量来枚举[i,j]这个子串时，统计完后，i++,j还要再返回i的位置，重新遍历，所以时间复杂度太高，为O(N^2)。

题目要求出子串中恰好包含k个辅音字母，我们可以先求出满足至少包含k个辅音字母的子串个数count(k)，再求出至少包含k+1个辅音字母的子串个数count(k+1)。而我们想要的结果刚好等于 count(k)-count(k+1)。其中求count(k)我们可以用滑动窗口实现。

具体过程（配图）：

具体过程（文字描述）：

1，进窗口，固定左端点i，让右端点j开始右移，直到找到一个满足要求的区间，

使用一个哈希表cur来统计区间中元音字母及其出现次数，使用一个变量cnt来统计区间中辅音字母的出现次数。

2，更新结果，当找到一个满足要求的区间，区间[i,j]满足包含所有的原因字母及至少包含k个辅音字母，这时，j就不需要继续往后移动了，因为后面的也必然满足要求。相当于我们找出了固定左端点i，所有满足要求的子串个数：n-j+1。更新结果，让ret+=n-j+1

3，出窗口，统计完结果后，左端点i右移，word[i]要出窗口，分两种情况：

如果word[i]为元音字母，将让哈希表中对应元音字母的出现次数--，如果减为0，就将该元音字母从哈希表中删除。

如果word[i]为辅音字母，将cnt--即可。

class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        // 求出子串中满足至少出现k个辅音字母的子串个数
        // 求出子串中满足至少出现k+1个辅音字母的子串个数
        // 结果就是count(k)-count(k+1)
        return count(word, k) - count(word, k + 1);
    }
       // 该函数用来求出至少出现k个辅音字母的子串个数
    long long count(string& word, int k) {
        set<char> owels = {'a', 'e', 'i', 'o', 'u'};
        long long ret=0,n=word.size();
        map<char,int> cur;//统计窗口中元音字母及其出现次数，方便窗口的移动
        int cnt=0;//统计辅音字母的个数

        for(int i=0,j=0;i<n;i++)
        {
            //进窗口
            //左端点word[i]固定，word[j]进窗口
            while(j<n&&(cnt<k||cur.size()<owels.size()))
            {
                if(owels.count(word[j]))
                cur[word[j]]++;  //元音字母
                else
                cnt++;   //辅因字母
                j++;
            }
            //更新结果
            if(cnt>=k&&cur.size()==owels.size())
            {
                ret+=n-j+1;
            }
            //出窗口
            //左端点右移,word[i]出窗口
            if(owels.count(word[i]))
            {
                //word[i]为元音字母
                cur[word[i]]--;
                if(cur[word[i]]==0)
                cur.erase(word[i]);
            }
            else
            {
                //word[i]为辅音字母
                cnt--;
            }
        }
        return ret;
    }
};

查看全文

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