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:
words[i] and result are decoded as one number without leading zeros.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 <= 51 <= words[i].length, result.length <= 7words[i], result contain only uppercase English letters.10.Problem Overview: You are given several words representing numbers where each character maps to a unique digit (0–9). The goal is to determine whether a digit assignment exists such that the sum of the first n‑1 words equals the final word. Leading characters cannot map to zero, and every letter must map to a distinct digit.
Approach 1: Backtracking Search (Exponential, ~O(10!) time, O(1) space)
This approach treats the puzzle as a digit assignment problem. First collect all unique characters across the input words. Then recursively assign digits from 0–9 while maintaining a used set so no digit is reused. After assigning digits to all characters, convert each word into a number and check whether the arithmetic equation holds. The key pruning rule prevents assigning 0 to leading characters. This brute-force backtracking search explores permutations of digits but prunes many invalid states early.
Approach 2: Constraint Satisfaction with Bit Masking (Optimized Backtracking, ~O(10!) worst case, O(1) space)
A more structured solution evaluates the equation column by column from right to left, similar to manual addition. Instead of constructing full numbers, maintain the running column sum and propagate carry values during recursion. A bit mask tracks which digits are already assigned, enabling constant-time digit availability checks. This turns the problem into a constraint satisfaction system where partial assignments are validated immediately. Early pruning dramatically reduces the search space because invalid column sums are discarded before exploring deeper states. This method combines ideas from math, string processing, and constraint-based backtracking.
Recommended for interviews: Start by explaining the basic backtracking permutation idea since it demonstrates understanding of the search space and constraints. Then move to the column-wise constraint approach with bit masking. Interviewers prefer this optimized strategy because it prunes invalid assignments early and models the arithmetic addition directly, which significantly reduces unnecessary recursion.
The backtracking approach involves recursively trying to assign digits to each character ensuring all constraints are met. By assigning digits to characters one by one, we calculate if they sum to the required result, backtracking if an assignment leads to an invalid state.
This solution explores different configurations and checks their validity, making it suitable due to the limited number of possible mappings.
This function begins by identifying all unique characters present in the words and result. If there are more than 10 unique characters, it's impossible to find a unique digit for each character, so it returns False immediately.
The function goes through all possible permutations of digits for these characters, ensuring no character that leads a word is assigned a zero (to avoid leading zeros). If any permutation yields a valid sum, True is returned. Otherwise, the function returns False after checking all permutations.
Python
JavaScript
Time Complexity: O(10^n) where n is the number of unique characters, considering the worst possibility of evaluating all permutations.
Space Complexity: O(1) as transformations exist within constant space primarily bound by auxiliary data structures.
The bit masking approach iteratively assigns digits to characters using bit masks to represent remaining available digits instead of checking conventional arrays. This method helps speed up operations by reducing assignments overhead and allows faster constraint checks.
This C++ solution uses standard library features to implement a bit masking technique for character-to-digit assignments, with recursive depth control to evaluate valid mappings.
It represents each character using its ASCII value and calculates potential word sums, verifying their equivalency to result values and returning True or False.
Time Complexity: O(10^n), consistent with permutations of n characters.
Space Complexity: O(1), largely leveraging existing data structures and small auxiliary vectors.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(10^n) where n is the number of unique characters, considering the worst possibility of evaluating all permutations. |
| Constraint Satisfaction with Bit Masking | Time Complexity: O(10^n), consistent with permutations of n characters. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Digit Assignment | O(10!) | O(1) | Good starting point to explain brute-force search and permutation generation |
| Constraint Satisfaction with Bit Masking | O(10!) worst case (heavily pruned) | O(1) | Preferred approach for interviews and competitive coding due to strong pruning |
Leetcode 1307: Verbal Arithmetic Puzzle (Leetcode Hard) • Algorithms Casts • 4,982 views views
Watch 5 more video solutions →Practice Verbal Arithmetic Puzzle with our built-in code editor and test cases.
Practice on FleetCode