Verbal Arithmetic Puzzle

Hard

#1217Time: O(P(10, U) * L), where `U` is the number of unique characters and `L` is the total number of characters in all strings. `P(10, U)` is the number of permutations (`10! / (10-U)!`). For each permutation, we perform a check that takes O(L) time. In the worst case (U=10), this is very slow.Space: O(U), where `U` is the number of unique characters (at most 10). This space is used to store the unique characters, the current permutation, and the character-to-digit map.2 companies

Patterns

Math Backtracking

Data structures

Array String

Companies

Atlassian Wells Fargo

Prompt

Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:

Each character is decoded as one digit (0 - 9).
No two characters can map to the same digit.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on the left side (words) will equal to the number on the right side (result).

Return true if the equation is solvable, otherwise return false.

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.

Constraints:

2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contain only uppercase English letters.
The number of different characters used in the expression is at most 10.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach tackles the problem by generating every possible assignment of digits to characters and checking if any of these assignments satisfy the given verbal arithmetic equation. It's a straightforward brute-force method that guarantees finding a solution if one exists, but at a high computational cost.

Algorithm

Extract Unique Characters: Iterate through all words and the result string to collect all unique characters into a list. Let the number of unique characters be U.
Generate Digit Permutations: Generate all possible assignments of U unique digits (from 0-9) to the U unique characters. This is equivalent to generating all permutations of size U from the 10 available digits.
Iterate and Check: For each generated mapping (a permutation of digits assigned to the list of characters): a. Build Map: Create a character-to-digit map based on the current permutation. b. Validate Leading Zeros: Check if any character that starts a word (with length > 1) or the result string is mapped to 0. If so, this mapping is invalid; discard it and proceed to the next permutation. c. Convert to Numbers: Using the valid mapping, convert each word string and the result string into their corresponding integer values. d. Verify Equation: Sum the integer values of the words and check if the sum equals the integer value of the result. e. Return True on Success: If the equation holds true, a solution has been found, so return true.
Return False: If all possible permutations are checked and no solution is found, return false.

Walkthrough

The core idea is to treat the problem as a permutation problem. First, we identify all unique characters present in the puzzle. If there are U unique characters, we need to find a mapping from these U characters to U distinct digits from the set {0, 1, ..., 9}. We can generate all permutations of U digits chosen from 10, and for each permutation, we test if it forms a valid solution.

A mapping is considered valid only if it satisfies two conditions: the sum of the numbers on the left side equals the number on the right, and no number has a leading zero (unless the number itself is 0, which is not the case here as word lengths are at least 1).

1import java.util.*;2 3class Solution {4    public boolean isSolvable(String[] words, String result) {5        Set<Character> charSet = new HashSet<>();6        for (String word : words) {7            for (char c : word.toCharArray()) charSet.add(c);8        }9        for (char c : result.toCharArray()) charSet.add(c);10 11        if (charSet.size() > 10) return false;12 13        List<Character> charList = new ArrayList<>(charSet);14        int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};15        16        return findPermutations(words, result, charList, digits, 0);17    }18 19    private boolean findPermutations(String[] words, String result, List<Character> charList, int[] digits, int index) {20        if (index == charList.size()) {21            return check(words, result, charList, digits);22        }23 24        // Generate permutations of digits for the characters25        for (int i = index; i < digits.length; i++) {26            swap(digits, index, i);27            if (findPermutations(words, result, charList, digits, index + 1)) {28                return true;29            }30            swap(digits, index, i); // backtrack31        }32        return false;33    }34 35    private void swap(int[] arr, int i, int j) {36        int temp = arr[i];37        arr[i] = arr[j];38        arr[j] = temp;39    }40 41    private boolean check(String[] words, String result, List<Character> charList, int[] p) {42        Map<Character, Integer> map = new HashMap<>();43        for (int i = 0; i < charList.size(); i++) {44            map.put(charList.get(i), p[i]);45        }46 47        // Check for leading zeros48        for (String word : words) {49            if (word.length() > 1 && map.get(word.charAt(0)) == 0) return false;50        }51        if (result.length() > 1 && map.get(result.charAt(0)) == 0) return false;52 53        long wordsSum = 0;54        for (String word : words) {55            long val = 0;56            for (char c : word.toCharArray()) {57                val = val * 10 + map.get(c);58            }59            wordsSum += val;60        }61 62        long resultVal = 0;63        for (char c : result.toCharArray()) {64            resultVal = resultVal * 10 + map.get(c);65        }66 67        return wordsSum == resultVal;68    }69}

Complexity

Time

O(P(10, U) * L), where `U` is the number of unique characters and `L` is the total number of characters in all strings. `P(10, U)` is the number of permutations (`10! / (10-U)!`). For each permutation, we perform a check that takes O(L) time. In the worst case (U=10), this is very slow.

Space

O(U), where `U` is the number of unique characters (at most 10). This space is used to store the unique characters, the current permutation, and the character-to-digit map.

Trade-offs

Pros

Conceptually simple and easy to understand.
Guaranteed to find a solution if one exists.

Cons

Highly inefficient as it explores all P(10, U) permutations without early termination.
Does not leverage the arithmetic constraints of the puzzle to prune the search space, leading to a lot of redundant checks.

This optimized approach uses backtracking combined with constraint propagation to solve the puzzle efficiently. Instead of generating full assignments and then checking them, it builds the assignment piece by piece, column by column, from right to left. The key advantage is its ability to prune the search space early. If a partial assignment violates the arithmetic rules in a single column, the algorithm immediately backtracks, avoiding exploration of countless invalid complete assignments that would stem from that partial one.

Algorithm

Pre-computation: a. Check for an impossible case: if any word is longer than the result, return false. b. Identify all characters that are the first letter of a word or the result (if length > 1). These characters cannot be mapped to 0. c. Reverse all words and the result string. This allows processing the equation from right to left (least significant digit to most significant), which is natural for addition.
Backtracking Function: Define a recursive function, e.g., solve(column, wordIndex, columnSum), which tries to find a valid assignment.
- column: The current digit position (column) being evaluated, starting from 0 (the rightmost digit).
- wordIndex: The index of the word currently being processed for the given column.
- columnSum: The running sum of digits for the current column, which starts with the carry-over from the previous column.
Recursive Logic:
- Word Traversal: The function recursively calls itself to move through all words for the current column, accumulating the columnSum.
- Character Assignment: If a character at the current position (words[wordIndex][column]) has not been assigned a digit, the function tries to assign every unused digit (0-9) to it. For each valid assignment (respecting the leading-zero rule), it makes a recursive call.
- Column Transition: Once all words for a column are processed (wordIndex reaches words.length), the function checks the sum against the corresponding character in the result. It calculates the required digit (columnSum % 10) and the newCarry (columnSum / 10). It then tries to assign/validate this digit for the result character and, if successful, recurses to the next column: solve(column + 1, 0, newCarry).
- Pruning: If at any point an assignment leads to a contradiction (e.g., a required digit is already used, or a sum doesn't match an already assigned result digit), the function returns false, pruning that entire search branch.
Base Case: The recursion stops when all columns of the result have been successfully processed (column == result.length()). A solution is found if the final carry is 0.

Walkthrough

We model the problem as a column-wise addition. By reversing the strings, we can process columns from index 0 upwards. The backtracking function explores the grid of characters, moving from word to word within a column, and then from column to column.

The state of our recursion can be defined by (column, wordIndex, columnSum). This state tells us we are trying to satisfy the sum for the given column, we are currently looking at words[wordIndex], and the sum of digits for this column so far is columnSum.

When a character is unassigned, we try to assign it an available digit. When we finish a column, we verify the sum against the result's digit for that column and calculate the carry to the next. This column-by-column check is the source of the pruning and efficiency gain.

1import java.util.*;2 3class Solution {4    private int[] charToDigit = new int[26];5    private boolean[] digitUsed = new boolean[10];6    private boolean[] isLeadingChar = new boolean[26];7    private String[] words;8    private String result;9 10    public boolean isSolvable(String[] words, String result) {11        this.words = new String[words.length];12        System.arraycopy(words, 0, this.words, 0, words.length);13        this.result = result;14        Arrays.fill(charToDigit, -1);15 16        int maxWordLen = 0;17        for (String word : words) {18            maxWordLen = Math.max(maxWordLen, word.length());19        }20        if (maxWordLen > result.length()) {21            return false;22        }23 24        // Identify leading characters based on original strings.25        for (String word : words) {26            if (word.length() > 1) isLeadingChar[word.charAt(0) - 'A'] = true;27        }28        if (result.length() > 1) isLeadingChar[result.charAt(0) - 'A'] = true;29 30        // Reverse all strings for right-to-left column processing.31        for (int i = 0; i < this.words.length; i++) {32            this.words[i] = new StringBuilder(this.words[i]).reverse().toString();33        }34        this.result = new StringBuilder(this.result).reverse().toString();35 36        return solve(0, 0, 0);37    }38 39    // Backtracking function: solve(column, wordIndex, columnSum)40    private boolean solve(int col, int wordIdx, int colSum) {41        // Base case: Finished processing all words for the current column.42        if (wordIdx == words.length) {43            if (col >= result.length()) {44                return colSum == 0;45            }46 47            char resChar = result.charAt(col);48            int resDigit = colSum % 10;49            int newCarry = colSum / 10;50 51            if (charToDigit[resChar - 'A'] != -1) { // Result char is assigned52                if (charToDigit[resChar - 'A'] == resDigit) {53                    return solve(col + 1, 0, newCarry);54                }55                return false;56            } else { // Result char is not assigned57                if (digitUsed[resDigit] || (isLeadingChar[resChar - 'A'] && resDigit == 0)) {58                    return false;59                }60                charToDigit[resChar - 'A'] = resDigit;61                digitUsed[resDigit] = true;62                if (solve(col + 1, 0, newCarry)) {63                    return true;64                }65                digitUsed[resDigit] = false;66                charToDigit[resChar - 'A'] = -1;67                return false;68            }69        }70 71        // If current word is shorter than the current column, move to next word.72        if (col >= words[wordIdx].length()) {73            return solve(col, wordIdx + 1, colSum);74        }75 76        // Process current character in the current word.77        char wordChar = words[wordIdx].charAt(col);78        if (charToDigit[wordChar - 'A'] != -1) { // Char is assigned79            return solve(col, wordIdx + 1, colSum + charToDigit[wordChar - 'A']);80        } else { // Char is not assigned, try all unused digits81            for (int digit = 0; digit < 10; digit++) {82                if (!digitUsed[digit] && !(isLeadingChar[wordChar - 'A'] && digit == 0)) {83                    charToDigit[wordChar - 'A'] = digit;84                    digitUsed[digit] = true;85                    if (solve(col, wordIdx + 1, colSum + digit)) {86                        return true;87                    }88                    digitUsed[digit] = false;89                    charToDigit[wordChar - 'A'] = -1;90                }91            }92            return false;93        }94    }95}

Complexity

Time

The worst-case time complexity is still exponential, as it's a search problem. However, it is significantly faster in practice than the brute-force permutation approach. The pruning based on column sums drastically reduces the effective search space.

Space

O(L + U), where `L` is the length of the result string and `U` is the number of unique characters. The space is dominated by the recursion stack depth (proportional to `L` * `words.length`) and storage for mappings (`U`). Given the constraints, this is effectively O(1).

Trade-offs

Pros

Much more efficient than brute-force due to early pruning of the search tree.
Intelligently uses the arithmetic structure of the problem to guide the search.

Cons

The implementation is significantly more complex than the brute-force approach.
The recursive logic with multiple state variables (column, wordIndex, sum) can be tricky to get right.

Solutions

Solution

1class Solution {2public3  boolean isSolvable(String[] words, String result) {4    Map<Character, Integer> letterDigitMap = new HashMap<Character, Integer>();5    Set<Character> leadingSet = new HashSet<Character>();6    int resultLength = result.length();7    for (String word : words) {8      if (word.length() > resultLength)9        return false;10      if (word.length() > 1)11        leadingSet.add(word.charAt(0));12    }13    if (result.length() > 1)14      leadingSet.add(result.charAt(0));15    boolean[] used = new boolean[10];16    int[] carry = new int[resultLength + 1];17    return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,18                            carry, 0, 0);19  }20public21  boolean depthFirstSearch(String[] words, String result,22                           Map<Character, Integer> letterDigitMap,23                           Set<Character> leadingSet, boolean[] used,24                           int[] carry, int position, int wordIndex) {25    if (position == result.length())26      return carry[position] == 0;27    else if (wordIndex < words.length) {28      String word = words[wordIndex];29      int wordLength = word.length();30      if (wordLength <= position ||31          letterDigitMap.containsKey(word.charAt(wordLength - position - 1)))32        return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,33                                carry, position, wordIndex + 1);34      else {35        char letter = word.charAt(wordLength - position - 1);36        int start = leadingSet.contains(letter) ? 1 : 0;37        for (int i = start; i <= 9; i++) {38          if (!used[i]) {39            used[i] = true;40            letterDigitMap.put(letter, i);41            boolean next =42                depthFirstSearch(words, result, letterDigitMap, leadingSet,43                                 used, carry, position, wordIndex + 1);44            used[i] = false;45            letterDigitMap.remove(letter);46            if (next)47              return true;48          }49        }50      }51      return false;52    } else {53      int remain = carry[position];54      for (String word : words) {55        if (word.length() > position) {56          char letter = word.charAt(word.length() - position - 1);57          remain += letterDigitMap.get(letter);58        }59      }60      carry[position + 1] = remain / 10;61      remain %= 10;62      char letter = result.charAt(result.length() - position - 1);63      if (letterDigitMap.containsKey(letter) &&64          letterDigitMap.get(letter) == remain)65        return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,66                                carry, position + 1, 0);67      else if (!letterDigitMap.containsKey(letter) && !used[remain] &&68               !(leadingSet.contains(letter) && remain == 0)) {69        used[remain] = true;70        letterDigitMap.put(letter, remain);71        boolean next =72            depthFirstSearch(words, result, letterDigitMap, leadingSet, used,73                             carry, position + 1, 0);74        used[remain] = false;75        letterDigitMap.remove(letter);76        return next;77      } else78        return false;79    }80  }81}

1// OJ: https://leetcode.com/problems/verbal-arithmetic-puzzle/ // Time: O(L! * L^2 * W) // Space: O(L) class Solution { unordered_map < char , int > m ; // map from char to the corresponding integer vector < char > chs ; // chars to consider, right most chars are first considered. unordered_set < char > leading ; // leading chars can't be zero int used [ 10 ] = {}; // digit `i` is used if `used[i] == 1` bool valid ( vector < string >& words , string result ) { // check if the current map `m` is valid int sum = 0 ; for ( int i = 0 ; i < result . size (); ++ i ) { for ( auto & w : words ) { if ( i >= w . size ()) continue ; char c = w [ w . size () - i - 1 ]; if ( m . count ( c ) == 0 ) return true ; sum += m [ c ]; } char c = result [ result . size () - i - 1 ]; if ( m . count ( c ) == 0 ) return true ; sum -= m [ c ]; if ( sum % 10 ) return false ; sum /= 10 ; } return true ; } bool dfs ( vector < string >& words , string result , int index ) { if ( index == chs . size ()) return true ; for ( int i = 0 ; i < 10 ; ++ i ) { if ( used [ i ] || ( i == 0 && leading . count ( chs [ index ]))) continue ; used [ i ] = 1 ; m [ chs [ index ]] = i ; if ( valid ( words , result ) && dfs ( words , result , index + 1 )) return true ; m . erase ( chs [ index ]); used [ i ] = 0 ; } return false ; } void addChar ( char ch ) { for ( char c : chs ) { if ( c == ch ) return ; } chs . push_back ( ch ); } public: bool isSolvable ( vector < string >& words , string result ) { for ( auto & w : words ) { if ( w . size () > result . size ()) return false ; if ( w . size () > 1 ) leading . insert ( w [ 0 ]); } if ( result . size () > 1 ) leading . insert ( result [ 0 ]); for ( int i = 0 ; i < result . size (); ++ i ) { for ( auto & w : words ) { if ( i < w . size ()) addChar ( w [ w . size () - i - 1 ]); } addChar ( result [ result . size () - i - 1 ]); } return dfs ( words , result , 0 ); } };

1class Solution:2    def isAnyMapping(self, words, row, col, bal, letToDig, digToLet, totalRows, totalCols):  # If traversed all columns. if col == totalCols : return bal == 0 # At the end of a particular column. if row == totalRows : return bal % 10 == 0 and self . isAnyMapping ( words , 0 , col + 1 , bal // 10 , letToDig , digToLet , totalRows , totalCols ) w = words [ row ] # If the current string 'w' has no character in the ('col')th index. if col >= len ( w ): return self . isAnyMapping ( words , row + 1 , col , bal , letToDig , digToLet , totalRows , totalCols ) # Take the current character in the variable letter. letter = w [ len ( w ) - 1 - col ] # Create a variable 'sign' to check whether we have to add it or subtract it. if row < totalRows - 1 : sign = 1 else : sign = - 1 # If we have a prior valid mapping, then use that mapping. # The second condition is for the leading zeros. if letter in letToDig and ( letToDig [ letter ] != 0 or ( letToDig [ letter ] == 0 and len ( w ) == 1 ) or col != len ( w ) - 1 ): return self . isAnyMapping ( words , row + 1 , col , bal + sign * letToDig [ letter ], letToDig , digToLet , totalRows , totalCols , ) # Choose a new mapping. else : for i in range ( 10 ): # If 'i'th mapping is valid then select it. if digToLet [ i ] == "-" and ( i != 0 or ( i == 0 and len ( w ) == 1 ) or col != len ( w ) - 1 ): digToLet [ i ] = letter letToDig [ letter ] = i # Call the function again with the new mapping. if self . isAnyMapping ( words , row + 1 , col , bal + sign * letToDig [ letter ], letToDig , digToLet , totalRows , totalCols , ): return True # Unselect the mapping. digToLet [ i ] = "-" if letter in letToDig : del letToDig [ letter ] # If nothing is correct then just return false. return False def isSolvable ( self , words , result ): # Add the string 'result' in the list 'words'. words . append ( result ) # Initialize 'totalRows' with the size of the list. totalRows = len ( words ) # Find the longest string in the list and set 'totalCols' with the size of that string. totalCols = max ( len ( word ) for word in words ) # Create a HashMap for the letter to digit mapping. letToDig = {} # Create a list for the digit to letter mapping. digToLet = [ "-" ] * 10 return self . isAnyMapping ( words , 0 , 0 , 0 , letToDig , digToLet , totalRows , totalCols )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem