Сколько раз данная строка встречается в массиве в диапазоне [l, r]

Опубликовано: 13 Января, 2022

Учитывая массив строк arr [] и два целых числа l и r , задача состоит в том, чтобы найти, сколько раз данная строка str встречается в массиве в диапазоне [l, r] (индексирование на основе 1). Обратите внимание, что строки содержат только строчные буквы.

Примеры:

Input: arr[] = {“abc”, “def”, “abc”}, L = 1, R = 2, str = “abc”
Output: 1
Input: arr[] = {“abc”, “def”, “abc”}, L = 1, R = 3, str = “ghf”
Output: 0

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать unordered_map для хранения индексов, в которых встречается i-я строка массива. Если данная строка отсутствует на карте, тогда ответ равен нулю, в противном случае выполните двоичный поиск по индексам данной строки, присутствующей на карте, и найдите количество вхождений строки в диапазоне [L, R].

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the number of occurrences of
int NumOccurrences(string arr[], int n, string str, int L, int R)
{
    // To store the indices of strings in the array
    unordered_map<string, vector<int> > M;
    for (int i = 0; i < n; i++) {
        string temp = arr[i];
        auto it = M.find(temp);
  
        // If current string doesn"t
        // have an entry in the map
        // then create the entry
        if (it == M.end()) {
            vector<int> A;
            A.push_back(i + 1);
            M.insert(make_pair(temp, A));
        }
        else {
            it->second.push_back(i + 1);
        }
    }
  
    auto it = M.find(str);
  
    // If the given string is not
    // present in the array
    if (it == M.end())
        return 0;
  
    // If the given string is present
    // in the array
    vector<int> A = it->second;
    int y = upper_bound(A.begin(), A.end(), R) - A.begin();
    int x = upper_bound(A.begin(), A.end(), L - 1) - A.begin();
  
    return (y - x);
}
  
// Driver code
int main()
{
    string arr[] = { "abc", "abcabc", "abc" };
    int n = sizeof(arr) / sizeof(string);
    int L = 1;
    int R = 3;
    string str = "abc";
  
    cout << NumOccurrences(arr, n, str, L, R);
  
    return 0;
}

Python3

# Python implementation of the approach
from bisect import bisect_right as upper_bound
from collections import defaultdict
  
# Function to return the number of occurrences of
def numOccurences(arr: list, n: int, string: str, L: int, R: int) -> int:
  
    # To store the indices of strings in the array
    M = defaultdict(lambda: list)
    for i in range(n):
        temp = arr[i]
  
        # If current string doesn"t
        # have an entry in the map
        # then create the entry
        if temp not in M:
            A = []
            A.append(i + 1)
            M[temp] = A
        else:
            M[temp].append(i + 1)
  
    # If the given string is not
    # present in the array
    if string not in M:
        return 0
  
    # If the given string is present
    # in the array
    A = M[string]
    y = upper_bound(A, R)
    x = upper_bound(A, L - 1)
  
    return (y - x)
  
# Driver Code
if __name__ == "__main__":
    arr = ["abc", "abcabc", "abc"]
    n = len(arr)
    L = 1
    R = 3
    string = "abc"
  
    print(numOccurences(arr, n, string, L, R))
  
# This code is contributed by
# sanjeev2552

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Сколько раз данная строка встречается в массиве в диапазоне [l, r]

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ