PROBLEM LINK:
Preparing Test-MATH88
Editorialist: Siddhartha Malladi
DIFFICULTY:
MEDIUM-HARD, HARD
PREREQUISITES:
Backtracking, DFS, Verbal Arithmetic
PROBLEM:
In simple words:
There are N words and a result word. We have to assign each character to a number(1 to 9) and replace the characters of N words and result words with corresponding numbers. Then if the sum of numbers of N words are equal to the result word number then print True.
Constraints:
Total number of unique characters in N words are not greater than 10. All input words and RESULT are in UPPER-CASE only!
- 2≤ N≤ 10
- 1≤ Length of The word ≤10
- 1≤ LengthofTheResult ≤11
EXPLANATION:
Suppose we have an equation; expressions are represented by words on left side and the result on right side. We have to check whether the equation is solvable under the following rules or not −
• Each character is decoded as one digit (0 to 9).
• Every pair of different characters must map to different digits.
• Each word[i] and result are decoded as a number where no leading zeros are present.
• Sum of numbers on left side will equal to the number on right side.
• We will check whether the equation is solvable or not.
So, if the input is like words = [“SEND”,“MORE”], result = “MONEY”,
Then the output will be True, as when we map the letters as follows:
Map ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0,‘R’->8, ‘Y’->‘2’,
Then “SEND” + “MORE” = “MONEY” is same as 9567 + 1085 = 10652.
For more details please refer this LINK
SOLUTIONS:
Editorialist's Solution
Time Complexity: O(n!)
Java Solution:
import java.*;
import java.util.*;
class Solution {
public boolean isSolvable(String[] words, String result) {
reverseWords(words);
result = new StringBuilder(result).reverse().toString();
return isSolvable(words, result, new HashMap<>(), new HashSet<>(), 0, 0, 0);
}
private void reverseWords(String[] words) {
for (int i = 0; i < words.length; i++) {
words[i] = new StringBuilder(words[i]).reverse().toString();
}
}
private boolean isSolvable(String[] words, String result, Map<Character, Integer> map, Set<Integer> used, int i, int j, int sum) {
if (i >= result.length()) {
return sum == 0;
}
if (j >= words.length) {
if (map.containsKey(result.charAt(i))) {
if (map.get(result.charAt(i)) != sum % 10) {
return false;
}
if (i + 1 == result.length() && map.get(result.charAt(i)) == 0) {
return false;
}
return isSolvable(words, result, map, used, i + 1, 0, sum / 10);
}
else if (!used.contains(sum % 10) && !(i + 1 == result.length() && sum % 10 == 0)) {
map.put(result.charAt(i), sum % 10);
used.add(sum % 10);
if (isSolvable(words, result, map, used, i + 1, 0, sum / 10)) {
return true;
}
used.remove(sum % 10);
map.remove(result.charAt(i));
}
return false;
}
if (i >= words[j].length()) {
return isSolvable(words, result, map, used, i, j + 1, sum);
}
if (map.containsKey(words[j].charAt(i))) {
if (i + 1 == words[j].length() && map.get(words[j].charAt(i)) == 0) {
return false;
}
return isSolvable(words, result, map, used, i, j + 1, sum + map.get(words[j].charAt(i)));
}
for (int g = 0; g < 10; g++) {
if (used.contains(g)) {
continue;
}
if (g == 0 && i + 1 == words[j].length()) {
continue;
}
map.put(words[j].charAt(i), g);
used.add(g);
if (isSolvable(words, result, map, used, i, j + 1, sum + g)) {
return true;
}
used.remove(g);
map.remove(words[j].charAt(i));
}
return false;
}
}
class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n;
n=sc.nextInt();
String vec[]=new String[n];
for(int i=0;i<n;i++){
vec[i]=sc.next();
}
String result;
result=sc.next();
Solution sol=new Solution();
if(sol.isSolvable(vec,result)){
System.out.println("true");
}
else{
System.out.println("false");
}
}
}