{x}
blog image

Verbal Arithmetic Puzzle

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.

Solution Explanation

This problem requires finding a valid mapping of letters to digits such that the sum of numbers represented by the words in the words array equals the number represented by the result string. The solution uses a backtracking approach with recursive function calls to explore all possible mappings.

Algorithm:

  1. Preprocessing:

    • The result string is added to the words array to treat it as part of the equation.
    • The maximum length among all strings (words and result) is determined to set the number of columns to process (digits in the numbers).

  2. Recursive Function isAnyMapping: This function is the core of the backtracking algorithm.

    • It takes the words array, current row (string index), col (digit index), running balance (bal), letter-to-digit mapping (letToDig), digit-to-letter mapping (digToLet), total number of rows, and total number of columns as input.
    • Base Cases:
      • If all columns are processed (col == totalCols), the function checks if the final balance is 0. If yes, a valid mapping is found.
      • If all rows are processed for the current column (row == totalRows), it checks if the balance is divisible by 10 (no carry-over) and recursively calls itself for the next column.
    • Recursive Step:
      • It processes each character (letter) of the current string (words[row]) in the current column.
      • If a letter already has a mapping in letToDig (and it's a valid mapping avoiding leading zeros), the function recursively calls itself with the existing mapping.
      • If there's no mapping for the letter, it tries all digits (0-9) that are not already assigned. For each trial:
        • It assigns the digit to the letter and updates letToDig and digToLet.
        • It recursively calls itself to check if this mapping leads to a solution.
        • If the recursive call returns true, a solution is found, and the function returns true.
        • If the recursive call returns false, the mapping is undone (backtracking).
    • If none of the mappings lead to a solution, the function returns false.

  3. isSolvable Function:

    • It initializes the letToDig and digToLet mappings.
    • It calls the isAnyMapping function to start the backtracking process.

Time Complexity: O(10^N), where N is the number of unique letters in the input. In the worst case, we might try all 10 possible digits for each unique letter. This is an upper bound, and the actual runtime might be significantly shorter due to backtracking and early pruning.

Space Complexity: O(N), primarily due to the letter-to-digit and digit-to-letter mapping structures.

Code Improvements:

The provided code is generally well-structured. However, some minor improvements could enhance readability and efficiency:

  • More descriptive variable names: Names like letToDig and digToLet are already quite clear, but using even more explicit names, like letterToDigitMap and digitToLetterMap, would enhance readability.
  • Error handling: Adding checks for invalid inputs (e.g., empty words or result) could make the code more robust.