Решение криптарифметических головоломок | Набор 2

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

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

Примеры:

Input: arr[][] = {“SEND”, “MORE”}, S = “MONEY”
Output: Yes
Explanation:
One of the possible ways is:
Map the characters as the following, ‘S’→ 9, ‘E’→5, ‘N’→6, ‘D’→7, ‘M’→1, ‘O’→0, ‘R’→8, ‘Y’→2.
Now, after encoding the strings “SEND”, “MORE”, and “MONEY”, modifies to 9567, 1085 and 10652 respectively.
Thus, the sum of the values of “SEND” and “MORE” is equal to (9567+1085 = 10652), which is equal to the value of the string “MONEY”.
Therefore, print “Yes”.
Input: arr[][] = {“SIX”, “SEVEN”, “SEVEN”}, S = “TWENTY”
Output: Yes
Explanation:
One of the possible ways is:
Map the characters as the following, ‘S’→ 6, ‘I’→5, ‘X’→0, ‘E’→8, ‘V’→7, ‘N’→2, ‘T’→1, ‘W’→’3’, ‘Y’→4.
Now, after encoding the strings “SIX”, “SEVEN”, and “TWENTY”, modifies to 650, 68782 and 138214 respectively.
Thus, the sum of the values of “SIX”, “SEVEN”, and “SEVEN” is equal to (650+ 68782+ 68782 = 138214), which is equal to the value of the string “TWENTY”.
Therefore, print “Yes”.

Здесь обсуждался набор 1 этой статьи, в котором массив строк имеет размер 2 .

Подход: Данная проблема может быть решена с помощью Backtracking. Выполните следующие шаги, чтобы решить проблему:

Инициализируйте три, arrayssay mp[26], Hash[26] и CharAtfront[26] для хранения сопоставленного значения алфавита, суммы значений позиции алфавита в каждой строке и если символ находится в начальном индексе любой строки.
Инициализируйте массив used[10] для хранения того, отображается ли число в какой-либо алфавит или нет.
Инициализируйте StringBuffersay уникальным , чтобы сохранить строку с каждым встречающимся алфавитом один раз.
Присвойте -1 каждому элементу массива mp .
Перебрать массив arr[] с помощью переменной i и выполнить следующие операции:
- Сохраните длину строки arr[i] в переменной M .
- Перебрать строку arr[i] с помощью переменной j и выполнить следующие операции:
  - Если mp[arr[i][j] – 'A'] равно -1 , тогда добавьте arr[i][j] в uniq и присвойте 0 mp[arr[i][j]-'A] .
  - Теперь увеличьте значение Hash[arr[i][j] -'A'] на 10 ^(Mj-1) .
  - Если arr[i].length() > 1 и j равно 0 , тогда пометьте true в arr[i][j] – 'A' в CharAtfront[] .
Переберите строку S и выполните те же задачи, что и для каждого массива Strings.
Заполните -1 для каждого элемента массива mp.
Определите рекурсивную функцию:
- Если i равно word.length() , тогда верните true , если S равно 0 . В противном случае вернуть false .
- Если mp[word[i]-'A'] не равно -1 , то рекурсивно вызов функция решает (слово, i+1, S+mp[слово[i]-'A']*Hash[слово[i]-'A], mp, используется), а затем возвращает возвращаемое ею значение.
- В противном случае инициализируйте переменную X как false и выполните итерацию по диапазону [0, 9], используя переменную j , и выполните следующие операции:
  - Перейти к следующей итерации в цикле, если выполняется любое из условий:
    - Если used[j] равно true .
    - Если CharAtfront[word[i]-'A'] равно 1 , а j равно 0 .
  - Теперь пометьте used[j] как true и присвойте j mp[word[i]-'A'].
  - После вышеописанных шагов вызовите функциюsolve(word,i+1,S+j*Hash[word[i]-'A'],mp, used), а затем выполните побитовое ИЛИ X с возвращаемым ею значением.
  - Теперь пометьте used[j] как false и присвойте -1 mp[word[i] – 'A'] для поиска с возвратом.
- Вернуть значение X .
Наконец, после выполнения вышеуказанных шагов, если значение, возвращаемое Solve(uniq, 0, 0, mp, used) , истинно, выведите « Да ». В противном случае выведите « Нет ».

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

Временная сложность: O(N*M+10!), где M — длина наибольшей строки.
Вспомогательное пространство: O(26)

Решение криптарифметических головоломок | Набор 2

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