Рубрики

Запросы, чтобы найти количество гласных в подстроках данной строки

Дана строка str длины N и Q запросов, где каждый запрос состоит из двух целых чисел L и R. Для каждого запроса задача состоит в том, чтобы найти количество гласных в подстроке str [L… R] .

Примеры:

Input: str = “geeksforgeeks”, q[][] = {{1, 3}, {2, 4}, {1, 9}}
Output:
2
1
4
Query 1: “eek” has 2 vowels.
Query 2: “eks” has 1 vowel.
Query 3: “eeksforge” has 2 vowels.

Input: str = “aaaa”, q[][] = {{1, 3}, {1, 4}}
Output:
3
3

Наивный подход: для каждого запроса просмотрите строку от L- го символа до R- го символа и найдите количество гласных.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define N 2

  
// Функция, которая возвращает true
// если ch гласный

bool isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e'

            || ch == 'i' || ch == 'o'

            || ch == 'u');

}

  
// Функция для возврата количества гласных
// в подстроке str [l ... r]

int countVowels(string str, int l, int r)

{

  

    // Для сохранения количества гласных

    int cnt = 0;

  

    // Для каждого символа в

    // индексный диапазон [l, r]

    for (int i = l; i <= r; i++) {

  

        // Если текущий символ

        // гласный

        if (isVowel(str[i]))

            cnt++;

    }

    return cnt;

}

  

void performQueries(string str, int queries[][N], int q)

{

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) {

  

        // Находим количество гласных

        // для текущего запроса

        cout << countVowels(str, queries[i][0],

                            queries[i][1]) << "\n";

    }

}

  
// Код драйвера

int main()

{

    string str = "geeksforgeeks";

    int queries[][N] = { { 1, 3 }, { 2, 4 }, { 1, 9 } };

    int q = (sizeof(queries)

             / sizeof(queries[0]));

  

    performQueries(str, queries, q);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

static int N = 2;

  
// Функция, которая возвращает true
// если ch гласный

static boolean isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e' || 

            ch == 'i' || ch == 'o' || 

            ch == 'u');

}

  
// Функция для возврата количества гласных
// в подстроке str [l ... r]

static int countVowels(String str, 

                       int l, int r)

{

  

    // Для сохранения количества гласных

    int cnt = 0;

  

    // Для каждого символа в

    // индексный диапазон [l, r]

    for (int i = l; i <= r; i++)

    {

  

        // Если текущий символ

        // гласный

        if (isVowel(str.charAt(i)))

            cnt++;

    }

    return cnt;

}

  

static void performQueries(String str, 

                           int queries[][], 

                           int q)

{

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Находим количество гласных

        // для текущего запроса

        System.out.println(countVowels(str, queries[i][0],

                                            queries[i][1]));

    }

}

  
// Код драйвера

public static void main(String[] args) 

{

    String str = "geeksforgeeks";

    int queries[][] = { { 1, 3 }, { 2, 4 }, 

                                  { 1, 9 } };

    int q = queries.length;

  

    performQueries(str, queries, q);

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 реализация подхода

N = 2

  
# Функция, которая возвращает true
# если ch гласный

def isVowel(ch) : 

  

    return (ch == 'a' or ch == 'e' or 

            ch == 'i' or ch == 'o' or

            ch == 'u'); 

  
# Функция для возврата количества гласных
# в подстроке str [l ... r]

def countVowels(string, l, r) :

  

    # Хранить количество гласных

    cnt = 0

  

    # Для каждого символа в

    # диапазон индекса [l, r]

    for i in range(l, r + 1) :

  

        # Если текущий символ

        # гласный

        if (isVowel(string[i])) :

            cnt += 1

  

    return cnt; 

  

def performQueries(string, queries, q) :

  

    # Для каждого запроса

    for i in range(q) :

  

        # Найти количество гласных

        # для текущего запроса

        print(countVowels(string, queries[i][0], 

                                  queries[i][1])); 

  
# Код драйвера

if __name__ == "__main__"

  

    string = "geeksforgeeks"

    queries = [ [ 1, 3 ],

                [ 2, 4 ], 

                [ 1, 9 ] ]; 

    q = len(queries) 

  

    performQueries(string, queries, q); 

  
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

  

class GFG

{

static int N = 2;

  
// Функция, которая возвращает true
// если ch гласный

static Boolean isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e' || 

            ch == 'i' || ch == 'o' || 

            ch == 'u');

}

  
// Функция для возврата количества гласных
// в подстроке str [l ... r]

static int countVowels(String str, 

                       int l, int r)

{

  

    // Для сохранения количества гласных

    int cnt = 0;

  

    // Для каждого символа в

    // индексный диапазон [l, r]

    for (int i = l; i <= r; i++)

    {

  

        // Если текущий символ

        // гласный

        if (isVowel(str[i]))

            cnt++;

    }

    return cnt;

}

  

static void performQueries(String str, 

                           int [,]queries, 

                           int q)

{

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Находим количество гласных

        // для текущего запроса

        Console.WriteLine(countVowels(str, queries[i, 0],

                                           queries[i, 1]));

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    String str = "geeksforgeeks";

    int [,]queries = { { 1, 3 }, { 2, 4 }, 

                                 { 1, 9 } };

    int q = queries.GetLength(0);

  

    performQueries(str, queries, q);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

2
1
4

Сложность времени: O (N * Q), где N — длина строки, а Q — количество запросов.

Эффективный подход: создайте префиксный массив pre [], где pre [i] будет хранить количество гласных в подстроке str [0… i] . Теперь количество гласных в диапазоне [L, R] можно легко вычислить в O (1) как pre [R] — pre [L — 1] .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define N 2

  
// Функция, которая возвращает true
// если ch гласный

bool isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e'

            || ch == 'i' || ch == 'o'

            || ch == 'u');

}

  

void performQueries(string str, int len,

                    int queries[][N], int q)

{

  

    // pre [i] будет хранить количество

    // гласные в подстроке str [0 ... i]

    int pre[len];

  

    if (isVowel(str[0]))

        pre[0] = 1;

    else

        pre[0] = 0;

  

    // Заполняем массив pre []

    for (int i = 1; i < len; i++) {

  

        // Если текущий символ гласный

        if (isVowel(str[i]))

            pre[i] = 1 + pre[i - 1];

  

        // Если это согласный

        else

            pre[i] = pre[i - 1];

    }

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) {

  

        // Находим количество гласных

        // для текущего запроса

        if (queries[i][0] == 0) {

            cout << pre[queries[i][1]] << "\n";

        }

        else {

            cout << (pre[queries[i][1]]

                     - pre[queries[i][0] - 1])

                 << "\n";

        }

    }

}

  
// Код драйвера

int main()

{

    string str = "geeksforgeeks";

    int len = str.length();

    int queries[][N] = { { 1, 3 }, { 2, 4 }, { 1, 9 } };

    int q = (sizeof(queries)

             / sizeof(queries[0]));

  

    performQueries(str, len, queries, q);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

static final int N = 2;

  
// Функция, которая возвращает true
// если ch гласный

static Boolean isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e' || 

            ch == 'i' || ch == 'o' ||

            ch == 'u');

}

  

static void performQueries(String str, int len,

                      int queries[][], int q)

{

  

    // pre [i] будет хранить количество

    // гласные в подстроке str [0 ... i]

    int []pre = new int[len];

  

    if (isVowel(str.charAt(0)))

        pre[0] = 1;

    else

        pre[0] = 0;

  

    // Заполняем массив pre []

    for (int i = 1; i < len; i++) 

    {

  

        // Если текущий символ гласный

        if (isVowel(str.charAt(i)))

            pre[i] = 1 + pre[i - 1];

  

        // Если это согласный

        else

            pre[i] = pre[i - 1];

    }

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Находим количество гласных

        // для текущего запроса

        if (queries[i][0] == 0

        {

            System.out.println(pre[queries[i][1]]);

        }

        else 

        {

            System.out.println((pre[queries[i][1]] - 

                                pre[queries[i][0] - 1]));

        }

    }

}

  
// Код драйвера

public static void main(String[] args)

{

    String str = "geeksforgeeks";

    int len = str.length();

    int queries[][] = { { 1, 3 }, 

                        { 2, 4 }, { 1, 9 } };

    int q = queries.length;

  

    performQueries(str, len, queries, q);

}
}

  
// Этот код предоставлен Rajput-Ji

Python 3

# Python 3 реализация подхода

N = 2

  
# Функция, которая возвращает true
# если ch гласный

def isVowel(ch):

    return (ch == 'a' or ch == 'e' or 

            ch == 'i' or ch == 'o' or

            ch == 'u')

  

def performQueries(str1, len1, queries, q):

      

    # pre [i] будет хранить количество

    # гласные в подстроке str [0 ... i]

    pre = [0 for i in range(len1)]

  

    if (isVowel(str1[0])):

        pre[0] = 1

    else:

        pre[0] = 0

  

    # Заполните массив pre []

    for i in range(0, len1, 1):

          

        # Если текущий символ гласный

        if (isVowel(str1[i])):

            pre[i] = 1 + pre[i - 1]

  

        # Если это согласный

        else:

            pre[i] = pre[i - 1]

  

    # Для каждого запроса

    for i in range(q):

          

        # Найти количество гласных

        # для текущего запроса

        if (queries[i][0] == 0):

            print(pre[queries[i][1]])

        else:

            print(pre[queries[i][1]] - 

                  pre[queries[i][0] - 1])

  
# Код драйвера

if __name__ == '__main__':

    str1 = "geeksforgeeks"

    len1 = len(str1)

    queries = [[1, 3], [2, 4], [1, 9]]

    q = len(queries)

  

    performQueries(str1, len1, queries, q)

  
# Этот код предоставлен Surendra_Gangwar

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

static readonly int N = 2;

  
// Функция, которая возвращает true
// если ch гласный

static Boolean isVowel(char ch)

{

  

    return (ch == 'a' || ch == 'e' || 

            ch == 'i' || ch == 'o' ||

            ch == 'u');

}

  

static void performQueries(String str, int len,

                       int [,]queries, int q)

{

  

    // pre [i] будет хранить количество

    // гласные в подстроке str [0 ... i]

    int []pre = new int[len];

  

    if (isVowel(str[0]))

        pre[0] = 1;

    else

        pre[0] = 0;

  

    // Заполняем массив pre []

    for (int i = 1; i < len; i++) 

    {

  

        // Если текущий символ гласный

        if (isVowel(str[i]))

            pre[i] = 1 + pre[i - 1];

  

        // Если это согласный

        else

            pre[i] = pre[i - 1];

    }

  

    // Для каждого запроса

    for (int i = 0; i < q; i++) 

    {

  

        // Находим количество гласных

        // для текущего запроса

        if (queries[i, 0] == 0) 

        {

            Console.WriteLine(pre[queries[i, 1]]);

        }

        else

        {

            Console.WriteLine((pre[queries[i, 1]] - 

                               pre[queries[i, 0] - 1]));

        }

    }

}

  
// Код драйвера

public static void Main(String[] args)

{

    String str = "geeksforgeeks";

    int len = str.Length;

    int [,]queries = { { 1, 3 }, 

                       { 2, 4 }, { 1, 9 } };

    int q = queries.GetLength(0);

  

    performQueries(str, len, queries, q);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

2
1
4

Сложность времени: O (N) для предварительного вычисления и O (1) для каждого запроса.

Рекомендуемые посты:

Запросы, чтобы найти количество гласных в подстроках данной строки

0.00 (0%) 0 votes