包含恰好 K 个不同元音的子字符串的数量

data structurec++server side programmingprogramming更新于 2024/10/3 1:45:00

在这个问题中,我们需要计算字符串 str 中恰好包含 K 个不同元音的子字符串的总数。我们可以通过两种不同的方式解决这个问题。第一种方法是遍历所有子字符串并计算每个子字符串中的元音数量。我们还可以使用 map 数据结构来优化第一种方法的代码。

问题陈述– 我们给出了长度为 N 的字符串 str。该字符串包含大写和小写字母字符。另外,我们给出了整数 K。我们需要找到 str 中恰好包含 K 个不同元音的子字符串的总数。

注意– 在这里,我们假设"a"和"A"相等。

示例

输入– str = "point",K = 2

输出– 6

解释– 恰好包含 2 个元音的 str 的子字符串为:'poi'、'oin'、'oint'、'poin'、'point' 和 'oi'。

输入– str = 'abcurso',K = 3

输出– 1

解释– str 的子字符串恰好包含 3 个元音,即 str 本身。

输入– str = 'aeiofd', K = 5

输出– 0

解释– 由于字符串仅包含 4 个元音,因此我们需要一个包含 5 个元音的子字符串。因此,不可能找到任何子字符串。

方法 1

在此方法中,我们将获得长度为 1 到 N 的子字符串。我们将检查每个子字符串中的元音总数。如果我们发现任何子字符串恰好包含 K 个元音,我们将计数值增加 1。

算法

  • 定义"cnt"变量以根据给定条件存储子字符串的数量,并定义"len"以存储字符串的长度。

  • 使用两个嵌套循环覆盖 str 的所有子字符串。

  • 从第 i 个索引开始获取子字符串,其长度为 (q – p + 1)。

  • 使用 cntDistVowel() 函数计算子字符串中的不同元音。

    • 在 cntDistVowel() 函数中,定义映射。

    • 使用 transform() 将字符串转换为小写方法。

    • 遍历字符串并更新字符串中每个字符的映射值。将值从 0 更新为 1。

    • 从映射中返回"a"、"e"、"I"、"o"、"u"键的值的总和。

  • 在 countKSub() 函数中,如果"dis_vowel"等于 K,则将"cnt"的值增加 1。

  • 返回"cnt"值。

示例

#include <bits/stdc++.h>
using namespace std;
int cntDistVowel(string sub) {
    // 创建 unordered_map 来存储子字符串中存在的元音
    unordered_map<char, int> mp;
    // 将 sub 转换为小写
    transform(sub.begin(), sub.end(), sub.begin(), ::tolower);
    // 遍历子字符串
    for (int p = 0; p < sub.length(); p++) {
        mp[sub[p]] = 1;
    }
    // 返回不同元音的总数
    return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countkSubs(string str, int k) {
    // 存储子字符串的总数
    int cnt = 0;
    int len = str.length();
    // 遍历字符串
    for (int p = 0; p < len; p++) {
      for (int q = p; q < len; q++) {
        // 获取从 p 到 q 的子字符串
        string sub = str.substr(p, q - p + 1);
        // 计算子字符串中的不同元音
        int dis_vowel = cntDistVowel(sub);
        // 如果不同元音的数量等于 k,则将 cnt 增加 1
        if (dis_vowel == k)
             cnt++;
      }
   }
   return cnt;
}
int main() {
    string str = "point";
    int K = 2;
    cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(str, K) << endl;
    return 0;
}

输出

包含恰好 2 个元音的子字符串数量为 6

时间复杂度 – O(N*N*N)。这里,O(N*N) 用于查找所有子字符串,O(N) 用于计算最大长度为 N 的子字符串中的不同元音。

空间复杂度 – O(N),因为我们使用"sub"变量来存储子字符串。

方法 2

此方法包含上述代码的优化版本。在这里,我们在从第 i 个索引开始遍历子字符串时更新映射中存在的字符。当我们找到任何包含恰好 K 个元音的子字符串时,我们会更新计数值。

算法

  • 初始化"cnt"和"len"变量。

  • 使用循环遍历字符串 str。

  • 定义"dist_vowel"变量以存储从索引 p 开始的子字符串中的总不同元音。此外,定义 26 个列表以存储子字符串中元音的存在

  • 使用嵌套循环获取 i 和 j 索引子字符串。

  • 使用 tolower() 函数将字符转换为小写并将其存储到"temp"变量中。

  • – 使用 isVowel() 函数检查当前字符是否为 bowel。如果是,且不在映射中,则将 dist_vowel 的值增加 1。同时,更新映射的值。

  • 如果"disst_vowel"的值等于 K,则增加"cnt"的值。

  • 如果"dist_vowel"的值大于 K,则中断嵌套循环。

  • 返回"cnt"的值。

示例

#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
   return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' );
}
int countkSubs(string alpha, int k) {
    int len = alpha.length();
    // 初始化计数
    int cnt = 0;
    // 覆盖所有子字符串
    for (int p = 0; p < len; p++) {
        // 存储不同元音的数量
        int dist_vowel = 0;
        // 存储字符的数量
        vector<int> map(26, 0);
        // 获取从 p 到 q 的子字符串
        for (int q = p; q < len; q++) {
            char temp = tolower(alpha[q]);
            // 如果当前字符是元音并且是新的,则将 dist_vowel 增加 1
            if (isVowel(temp) && map[temp - 'a'] == 0)
            dist_vowel++;
            // 将字符计数增加 1
            map[temp - 'a']++;
            // 如果不同元音的数量为 k,则将计数增加 1
            if (dist_vowel == k)
            cnt++;
            // 如果不同元音的数量超过 k,则中断
            if (dist_vowel > k)
            break;
       }
   }
   return cnt;
}
int main() {
    string alpha = "point";
    int K = 2;
    cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(alpha, K) << endl;
    return 0;
}

输出

包含恰好 2 个元音的子字符串数量为 6

时间复杂度 – O(N*N),因为我们使用嵌套循环。

空间复杂度 – O(26) ~ O(1),因为我们用于存储子字符串中元音的存在。

我们学习了两种解决问题的方法。第一种方法是朴素方法,第二种方法是优化方法。在这里,我们解决了计算包含恰好 K 个不同元音的子字符串数量的问题。程序员可以解决计算包含恰好 K 个元音的子字符串数量的问题。


相关文章