Сгенерируйте все возможные строки, образованные заменой букв заданными соответствующими символами.

Опубликовано: 22 Сентября, 2022

Дана строка S , состоящая из N символов, и массив M[] пар символов, такой что любой символ M[i][0] можно заменить на символ M[i][1] в строке S , задача состоит в следующем: сгенерировать все возможные строки, образованные заменой некоторых символов строки соответствующими символами в массиве M[] .

Примеры:

Input: S = “aBc”, M = {‘a’ : ‘$’, ‘B’ : ‘#’, ‘c’ : ‘^’}
Output:
aBc
aB^
a#c
a#^
$Bc
$B^
$#c
$#^ 

Input: S = “a”, M={‘a’ : ‘$’}
Output:
a
$

Подход: данная проблема может быть решена с помощью Backtracking для генерации всех возможных строк путем замены каждого символа сопоставленным символом в массиве M[] . Выполните следующие шаги, чтобы решить проблему:

  • Сохраните все пары отображенных символов в массиве M[] на карте, скажем Map .
  • Определите рекурсивную функцию, скажем, generateLetters(S, P) , где S — измененная строка, а P — индекс текущего символа:
    • Проверьте базовый случай, т. е. если индекс P равен N , то напечатайте строку S и вернитесь.
    • Не изменяйте текущий символ и рекурсивно вызывайте функцию generateLetters(S, P + 1) .
    • Теперь замените символ S[P] соответствующим символом на карте M и вызовите функцию generateLetters(S, P+1) .
  • После выполнения вышеуказанных шагов вызовите функцию generateLetters(S, 0) для вывода всех возможных строк.

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

Временная сложность: O(N* 2N )
Вспомогательное пространство: O(1)

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