Cryptarithmetic

1. You are given three strings s1, s2 and s3.
2. First two are supposed to add and form third. s1 + s2 = s3
3. You have to map each individual character to a digit, so that the above equation holds true.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing the signature. The judge can't force you but intends you to teach a concept.

Input Format

Three strings
s1
s2
s3

Output Format

Check the sample output and question video

Question Video Constraints

1 <= length of s1,s2,s3 <= 10

Sample Input

team
pep
toppr

Sample Output

a-3 e-9 m-4 o-1 p-2 r-6 t-0 
a-3 e-9 m-5 o-1 p-2 r-7 t-0 
a-3 e-9 m-6 o-1 p-2 r-8 t-0 
a-4 e-9 m-2 o-1 p-3 r-5 t-0 
a-4 e-9 m-5 o-1 p-3 r-8 t-0 
a-5 e-9 m-2 o-1 p-4 r-6 t-0 
a-5 e-9 m-3 o-1 p-4 r-7 t-0 
a-6 e-9 m-2 o-1 p-5 r-7 t-0 
a-6 e-9 m-3 o-1 p-5 r-8 t-0 
a-7 e-9 m-2 o-1 p-6 r-8 t-0 

• Editorial

  Let us go through the rules again:

  Each character must be mapped with a number between 0 to 9. Each number can be used once only. For example - if 9 is mapped to 'a', then it cannot be mapped to any other letter. There will be one to one mapping..

  We can observe that we can solve this question by recursion and backtracking. We will first find a string that contains unique characters of s1,s2 and s3 using hashmap. Then we will assign every number from 0 to 9 to every character of this unique string. If we reach at the end of this string we will check whether the condition s1 + s2 = s3 holds true. If it is true, we will display the answer and return.

  To maintain the one to one mapping, we will use an auxiliary Boolean array of size 10 to store whether the current number has been used or not. If it is used we will mark that position as true in pre-order and for the further calls, we will not be able to use it again. In post-order we will unmark so it can be used again. Also, we will use a hashmap to store what value has been assigned to a character. Initially hashmap will contain every unique character as a key and -1 as a value for all the keys. In pre-order, we will mark the number we assigned to that number as value and in post order we will assign -1 again.

  Signature:

  public static void solution(String unique, int idx, HashMap
                                   charIntMap, boolean[] usedNumbers,
                                              String s1, String s2, String s3) {

  unique - substring containing all the unique characters of s1,s2 and s3.

  idx - current index

  charIntMap - Hashmap that will have initially all the characters of unique substring as key and -1 as value.

  usedNumbers - an auxiliary array to store which numbers from 0 to 9 have been used.

  s1,s2 and s3 - input substring

  Code:

  public static void solution(String unique, int idx, HashMap
   charIntMap, boolean[] usedNumbers,
                                              String s1, String s2, String s3) {
                                        if (idx == unique.length()) {
                                            int num1 = getNum(s1, charIntMap);
                                            int num2 = getNum(s2, charIntMap);
                                            int num3 = getNum(s3, charIntMap);
                                            if (num1 + num2 == num3) {
                                                for (int i = 0; i < 26; i++) {
                                                    char ch = (char) ('a' + i);
                                                    if (charIntMap.containsKey(ch)) {
                                                        System.out.print(ch + "-" + charIntMap.get(ch) + " ");
                                                    }
                                                }
                                                System.out.println();
                                            }
                                  
                                            return;
                                        }
                                  
                                        char ch = unique.charAt(idx);
                                        for (int num = 0; num <= 9; num++) {
                                            if (usedNumbers[num] == false) {
                                                usedNumbers[num] = true;
                                                charIntMap.put(ch, num);
                                                solution(unique, idx + 1, charIntMap, usedNumbers, s1, s2, s3);
                                                charIntMap.put(ch, -1);
                                                usedNumbers[num] = false;
                                            }
                                        }
                                  }
                                  public static int getNum(String s, HashMap
   charIntMap){
                                       String num = "";
                                  
                                       for(int i = 0; i < s.length(); i++){
                                  	  char ch = s.charAt(i);
                                  	  num += charIntMap.get(ch);
                                       }
                                       return Integer.parseInt(num); 
                                  }

  java falseCode Explained:

  In recursion, the characters of unique string will be at level.

  We will assign each character a number from 0 to 9 and mark the number we visited as true and mark the number we assigned to the character in hashmap in pre-order. We will call recursive function for the next level and in post-order we will unmark the number we used and put -1 for that character in hashmap.

  When index will be equal to the length of the unique substring, we will check whether the s1 + s2 == s3. If it is, we will print all the values we assigned to the character lexicographically.

  We will return as all the characters have been used value.

  Base Case:

  When idx will be equal to the length of the unique substring, then we will check whether the numbers we assigned satisfy the given condition or not. To check that we will iterate throught the s1 and generate the number we will get from it. Similarly, for s2 and s3. If the numbers returned satisfy the condition, we will print the answer in lexicographical manner.

  Code to generate the respective numbers :

  public static int getNum(String s, HashMap charIntMap){
                                       String num = "";
                                  
                                       for(int i = 0; i < s.length(); i++){
                                    char ch = s.charAt(i);
                                    num += charIntMap.get(ch);
                                       }
                                       return Integer.parseInt(num);
                                  }

  Dry Run:

  Input s1 = SEND, s2 = MORE and s3 = MONEY

  Unique string will be SENDMOREY

  This is how recursion tree will look like:

  

  We see that each unique character is assigned a number from 0 to 9 and at next level, the number assigned before is not used again.

• Asked in Companies
• Related Topics