Подсчет N-значных чисел, не имеющих префиксов

Учитывая целое число N и вектор префиксов строк [], задача состоит в том, чтобы вычислить общее количество возможных строк длины N от символов '0' до '9' . так что данные префиксы нельзя использовать ни в одной из строк.

Примеры:

Input: N = 3, prefixes = {“42”}
Output: 990
Explanation: All string except{“420”, “421”, “422”, “423”, “424”, “425”, “426”, “427”, “428”, “429”} are valid.

Input: N = 5, prefixes[] = { “0”, “1”, “911” }
Output: 79900

Подход: общее количество возможных строк с длиной равно (10^N) , так как для каждого места в строке есть 10 вариантов выбора символа. Вместо подсчета общего количества хороших строк вычтите общее количество плохих строк из общего количества строк. Перед повторением префиксов объединение префиксов с тем же начальным символом, что и префикс большей длины, может привести к вычитанию некоторых повторений. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную total как 10 ^N .
• Инициализировать карту<int, vector<string>> mp[].
• Перебрать диапазон [0, M), используя переменную i , и выполнить следующие задачи:
  • Вставьте значение prefixes[i] в вектор карты mp[prefixes[i]-'0'].
• Инициализируйте вектор new_prefixes[] .
• Пройдите по карте mp[] с помощью переменной x и выполните следующие задачи:
  • Инициализируйте переменную mn как N .
  • Пройдите вектор x.second, используя переменную p , и выполните следующие задачи:
    • Установите значение mn как минимум mn или p.length() .
  • Пройдите вектор x.second, используя переменную p , и выполните следующие задачи:
    • Если p.length() меньше, чем mn, то вставьте p в вектор new_prefixes[] .
• Перебрать диапазон [0, new_prefixes.size()) с помощью переменной i и выполнить следующие задачи:
  • Вычтите значение int(pow(10, N – new_prefixes[i].length())+ 0,5) из переменной total.
• После выполнения вышеуказанных шагов выведите значение total в качестве ответа.

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

Временная сложность: O(M), где M — размер векторных префиксов[]
Вспомогательный пробел: O(M*K), где K — максимальная длина строки.