# Verbal Arithmetic Puzzle
**Difficulty:** HARD
[External](https://leetcode.com/problems/verbal-arithmetic-puzzle)
Canonical: https://scaleengineer.com/dsa/problems/verbal-arithmetic-puzzle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo)
---
## Problem
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
## Brute-force with Permutations
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.
**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.
**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.
### Explanation
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).

```java
import java.util.*;

class Solution {
    public boolean isSolvable(String[] words, String result) {
        Set<Character> charSet = new HashSet<>();
        for (String word : words) {
            for (char c : word.toCharArray()) charSet.add(c);
        }
        for (char c : result.toCharArray()) charSet.add(c);

        if (charSet.size() > 10) return false;

        List<Character> charList = new ArrayList<>(charSet);
        int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        return findPermutations(words, result, charList, digits, 0);
    }

    private boolean findPermutations(String[] words, String result, List<Character> charList, int[] digits, int index) {
        if (index == charList.size()) {
            return check(words, result, charList, digits);
        }

        // Generate permutations of digits for the characters
        for (int i = index; i < digits.length; i++) {
            swap(digits, index, i);
            if (findPermutations(words, result, charList, digits, index + 1)) {
                return true;
            }
            swap(digits, index, i); // backtrack
        }
        return false;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private boolean check(String[] words, String result, List<Character> charList, int[] p) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < charList.size(); i++) {
            map.put(charList.get(i), p[i]);
        }

        // Check for leading zeros
        for (String word : words) {
            if (word.length() > 1 && map.get(word.charAt(0)) == 0) return false;
        }
        if (result.length() > 1 && map.get(result.charAt(0)) == 0) return false;

        long wordsSum = 0;
        for (String word : words) {
            long val = 0;
            for (char c : word.toCharArray()) {
                val = val * 10 + map.get(c);
            }
            wordsSum += val;
        }

        long resultVal = 0;
        for (char c : result.toCharArray()) {
            resultVal = resultVal * 10 + map.get(c);
        }

        return wordsSum == resultVal;
    }
}
```
### Algorithm
1.  **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`.
2.  **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.
3.  **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`.
4.  **Return False**: If all possible permutations are checked and no solution is found, return `false`.

## Optimized Backtracking with Column-wise Pruning
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.
**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).
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private int[] charToDigit = new int[26];
    private boolean[] digitUsed = new boolean[10];
    private boolean[] isLeadingChar = new boolean[26];
    private String[] words;
    private String result;

    public boolean isSolvable(String[] words, String result) {
        this.words = new String[words.length];
        System.arraycopy(words, 0, this.words, 0, words.length);
        this.result = result;
        Arrays.fill(charToDigit, -1);

        int maxWordLen = 0;
        for (String word : words) {
            maxWordLen = Math.max(maxWordLen, word.length());
        }
        if (maxWordLen > result.length()) {
            return false;
        }

        // Identify leading characters based on original strings.
        for (String word : words) {
            if (word.length() > 1) isLeadingChar[word.charAt(0) - 'A'] = true;
        }
        if (result.length() > 1) isLeadingChar[result.charAt(0) - 'A'] = true;

        // Reverse all strings for right-to-left column processing.
        for (int i = 0; i < this.words.length; i++) {
            this.words[i] = new StringBuilder(this.words[i]).reverse().toString();
        }
        this.result = new StringBuilder(this.result).reverse().toString();

        return solve(0, 0, 0);
    }

    // Backtracking function: solve(column, wordIndex, columnSum)
    private boolean solve(int col, int wordIdx, int colSum) {
        // Base case: Finished processing all words for the current column.
        if (wordIdx == words.length) {
            if (col >= result.length()) {
                return colSum == 0;
            }

            char resChar = result.charAt(col);
            int resDigit = colSum % 10;
            int newCarry = colSum / 10;

            if (charToDigit[resChar - 'A'] != -1) { // Result char is assigned
                if (charToDigit[resChar - 'A'] == resDigit) {
                    return solve(col + 1, 0, newCarry);
                }
                return false;
            } else { // Result char is not assigned
                if (digitUsed[resDigit] || (isLeadingChar[resChar - 'A'] && resDigit == 0)) {
                    return false;
                }
                charToDigit[resChar - 'A'] = resDigit;
                digitUsed[resDigit] = true;
                if (solve(col + 1, 0, newCarry)) {
                    return true;
                }
                digitUsed[resDigit] = false;
                charToDigit[resChar - 'A'] = -1;
                return false;
            }
        }

        // If current word is shorter than the current column, move to next word.
        if (col >= words[wordIdx].length()) {
            return solve(col, wordIdx + 1, colSum);
        }

        // Process current character in the current word.
        char wordChar = words[wordIdx].charAt(col);
        if (charToDigit[wordChar - 'A'] != -1) { // Char is assigned
            return solve(col, wordIdx + 1, colSum + charToDigit[wordChar - 'A']);
        } else { // Char is not assigned, try all unused digits
            for (int digit = 0; digit < 10; digit++) {
                if (!digitUsed[digit] && !(isLeadingChar[wordChar - 'A'] && digit == 0)) {
                    charToDigit[wordChar - 'A'] = digit;
                    digitUsed[digit] = true;
                    if (solve(col, wordIdx + 1, colSum + digit)) {
                        return true;
                    }
                    digitUsed[digit] = false;
                    charToDigit[wordChar - 'A'] = -1;
                }
            }
            return false;
        }
    }
}
```
### Algorithm
1.  **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.
2.  **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.
3.  **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.
4.  **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.

# Solutions
### Java

```java
class Solution {
public
  boolean isSolvable(String[] words, String result) {
    Map<Character, Integer> letterDigitMap = new HashMap<Character, Integer>();
    Set<Character> leadingSet = new HashSet<Character>();
    int resultLength = result.length();
    for (String word : words) {
      if (word.length() > resultLength)
        return false;
      if (word.length() > 1)
        leadingSet.add(word.charAt(0));
    }
    if (result.length() > 1)
      leadingSet.add(result.charAt(0));
    boolean[] used = new boolean[10];
    int[] carry = new int[resultLength + 1];
    return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,
                            carry, 0, 0);
  }
public
  boolean depthFirstSearch(String[] words, String result,
                           Map<Character, Integer> letterDigitMap,
                           Set<Character> leadingSet, boolean[] used,
                           int[] carry, int position, int wordIndex) {
    if (position == result.length())
      return carry[position] == 0;
    else if (wordIndex < words.length) {
      String word = words[wordIndex];
      int wordLength = word.length();
      if (wordLength <= position ||
          letterDigitMap.containsKey(word.charAt(wordLength - position - 1)))
        return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,
                                carry, position, wordIndex + 1);
      else {
        char letter = word.charAt(wordLength - position - 1);
        int start = leadingSet.contains(letter) ? 1 : 0;
        for (int i = start; i <= 9; i++) {
          if (!used[i]) {
            used[i] = true;
            letterDigitMap.put(letter, i);
            boolean next =
                depthFirstSearch(words, result, letterDigitMap, leadingSet,
                                 used, carry, position, wordIndex + 1);
            used[i] = false;
            letterDigitMap.remove(letter);
            if (next)
              return true;
          }
        }
      }
      return false;
    } else {
      int remain = carry[position];
      for (String word : words) {
        if (word.length() > position) {
          char letter = word.charAt(word.length() - position - 1);
          remain += letterDigitMap.get(letter);
        }
      }
      carry[position + 1] = remain / 10;
      remain %= 10;
      char letter = result.charAt(result.length() - position - 1);
      if (letterDigitMap.containsKey(letter) &&
          letterDigitMap.get(letter) == remain)
        return depthFirstSearch(words, result, letterDigitMap, leadingSet, used,
                                carry, position + 1, 0);
      else if (!letterDigitMap.containsKey(letter) && !used[remain] &&
               !(leadingSet.contains(letter) && remain == 0)) {
        used[remain] = true;
        letterDigitMap.put(letter, remain);
        boolean next =
            depthFirstSearch(words, result, letterDigitMap, leadingSet, used,
                             carry, position + 1, 0);
        used[remain] = false;
        letterDigitMap.remove(letter);
        return next;
      } else
        return false;
    }
  }
}

```

### CPP

```cpp
// 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 ); } };
```

### Python

```python
class Solution:
    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 )

```