Three-Word Additive Cryptarithmetic Solver
MediumUpdated: Oct 12, 2025
Problem
A cryptarithmetic puzzle is a mathematical game where the digits of some numbers are represented by letters. Each letter represents a unique digit.
For example, a puzzle of the form:
SEND
+ MORE
-----
MONEY
may have the solution:
{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}
Given a three-word puzzle like the one above, create an algorithm that finds a solution.
Examples
Example 1
Input: word1 = "SEND", word2 = "MORE", result = "MONEY"
Output: {'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}
Explanation: When substituted: 9567 + 1085 = 10652, which matches the constraint.
Example 2
Input: word1 = "TWO", word2 = "TWO", result = "FOUR"
Output: {'T': 7, 'W': 3, 'O': 4, 'F': 1, 'U': 0, 'R': 6}
Explanation: When substituted: 734 + 734 = 1468, which satisfies the equation.
Example 3
Input: word1 = "I", word2 = "BB", result = "BIC"
Output: {'I': 1, 'B': 9, 'C': 8}
Explanation: When substituted: 1 + 99 = 100, but this doesn't work. Correct solution: I=1, B=0, C=1 gives 1 + 00 = 01, but leading zeros aren't allowed for multi-digit numbers.
Solutions
Method 1 – Backtracking with Constraint Satisfaction
Intuition
This is a classic constraint satisfaction problem where we need to assign unique digits (0-9) to letters such that the arithmetic equation holds. We can use backtracking to systematically try different digit assignments and validate the constraint at each step.
The key insight is that we need to ensure: (1) each letter maps to a unique digit, (2) no leading zeros in multi-digit numbers, and (3) the arithmetic equation is satisfied.
Approach
- Extract unique letters from all three words to determine variables to assign
- Identify leading letters that cannot be zero (first letter of multi-digit words)
- Use backtracking to assign digits 0-9 to letters:
- Try each available digit for the current letter
- Check constraints (no leading zeros, unique assignments)
- Recursively assign remaining letters
- Validate the arithmetic equation when all letters are assigned
- Backtrack if constraints are violated
- Convert words to numbers using the letter-to-digit mapping and verify the equation
- Return the first valid solution found
Code
C++
class Solution {
private:
vector<char> letters;
unordered_set<char> leading;
unordered_map<char, int> mapping;
vector<bool> used;
string w1, w2, res;
long long wordToNum(const string& word) {
long long num = 0;
for (char c : word) {
num = num * 10 + mapping[c];
}
return num;
}
bool isValid() {
return wordToNum(w1) + wordToNum(w2) == wordToNum(res);
}
bool solve(int idx) {
if (idx == letters.size()) {
return isValid();
}
char ch = letters[idx];
for (int digit = 0; digit <= 9; digit++) {
if (used[digit]) continue;
if (digit == 0 && leading.count(ch)) continue;
mapping[ch] = digit;
used[digit] = true;
if (solve(idx + 1)) return true;
used[digit] = false;
mapping.erase(ch);
}
return false;
}
public:
unordered_map<char, int> solvePuzzle(string word1, string word2, string result) {
w1 = word1; w2 = word2; res = result;
unordered_set<char> unique;
for (char c : word1 + word2 + result) {
unique.insert(c);
}
for (char c : unique) {
letters.push_back(c);
}
if (word1.length() > 1) leading.insert(word1[0]);
if (word2.length() > 1) leading.insert(word2[0]);
if (result.length() > 1) leading.insert(result[0]);
used.resize(10, false);
if (solve(0)) return mapping;
return {};
}
};
Go
func solvePuzzle(word1, word2, result string) map[rune]int {
allChars := word1 + word2 + result
unique := make(map[rune]bool)
for _, c := range allChars {
unique[c] = true
}
var letters []rune
leading := make(map[rune]bool)
for c := range unique {
letters = append(letters, c)
}
if len(word1) > 1 {
leading[rune(word1[0])] = true
}
if len(word2) > 1 {
leading[rune(word2[0])] = true
}
if len(result) > 1 {
leading[rune(result[0])] = true
}
mapping := make(map[rune]int)
used := make([]bool, 10)
var solve func(int) bool
solve = func(idx int) bool {
if idx == len(letters) {
return wordToNum(word1, mapping) + wordToNum(word2, mapping) == wordToNum(result, mapping)
}
ch := letters[idx]
for digit := 0; digit <= 9; digit++ {
if used[digit] {
continue
}
if digit == 0 && leading[ch] {
continue
}
mapping[ch] = digit
used[digit] = true
if solve(idx + 1) {
return true
}
used[digit] = false
delete(mapping, ch)
}
return false
}
if solve(0) {
return mapping
}
return make(map[rune]int)
}
func wordToNum(word string, mapping map[rune]int) int64 {
var num int64
for _, c := range word {
num = num*10 + int64(mapping[c])
}
return num
}
Java
class Solution {
private List<Character> letters;
private Set<Character> leading;
private Map<Character, Integer> mapping;
private boolean[] used;
private String w1, w2, res;
private long wordToNum(String word) {
long num = 0;
for (char c : word.toCharArray()) {
num = num * 10 + mapping.get(c);
}
return num;
}
private boolean isValid() {
return wordToNum(w1) + wordToNum(w2) == wordToNum(res);
}
private boolean solve(int idx) {
if (idx == letters.size()) {
return isValid();
}
char ch = letters.get(idx);
for (int digit = 0; digit <= 9; digit++) {
if (used[digit]) continue;
if (digit == 0 && leading.contains(ch)) continue;
mapping.put(ch, digit);
used[digit] = true;
if (solve(idx + 1)) return true;
used[digit] = false;
mapping.remove(ch);
}
return false;
}
public Map<Character, Integer> solvePuzzle(String word1, String word2, String result) {
w1 = word1; w2 = word2; res = result;
Set<Character> unique = new HashSet<>();
for (char c : (word1 + word2 + result).toCharArray()) {
unique.add(c);
}
letters = new ArrayList<>(unique);
leading = new HashSet<>();
mapping = new HashMap<>();
used = new boolean[10];
if (word1.length() > 1) leading.add(word1.charAt(0));
if (word2.length() > 1) leading.add(word2.charAt(0));
if (result.length() > 1) leading.add(result.charAt(0));
if (solve(0)) return new HashMap<>(mapping);
return new HashMap<>();
}
}
Kotlin
class Solution {
private lateinit var letters: List<Char>
private val leading = mutableSetOf<Char>()
private val mapping = mutableMapOf<Char, Int>()
private val used = BooleanArray(10)
private lateinit var w1: String
private lateinit var w2: String
private lateinit var res: String
private fun wordToNum(word: String): Long {
var num = 0L
for (c in word) {
num = num * 10 + mapping[c]!!
}
return num
}
private fun isValid(): Boolean {
return wordToNum(w1) + wordToNum(w2) == wordToNum(res)
}
private fun solve(idx: Int): Boolean {
if (idx == letters.size) {
return isValid()
}
val ch = letters[idx]
for (digit in 0..9) {
if (used[digit]) continue
if (digit == 0 && ch in leading) continue
mapping[ch] = digit
used[digit] = true
if (solve(idx + 1)) return true
used[digit] = false
mapping.remove(ch)
}
return false
}
fun solvePuzzle(word1: String, word2: String, result: String): Map<Char, Int> {
w1 = word1
w2 = word2
res = result
val unique = (word1 + word2 + result).toSet()
letters = unique.toList()
if (word1.length > 1) leading.add(word1[0])
if (word2.length > 1) leading.add(word2[0])
if (result.length > 1) leading.add(result[0])
return if (solve(0)) mapping.toMap() else emptyMap()
}
}
Python
class Solution:
def solvePuzzle(self, word1: str, word2: str, result: str) -> dict[str, int]:
unique_chars = set(word1 + word2 + result)
letters = list(unique_chars)
# Leading characters cannot be zero
leading = set()
if len(word1) > 1:
leading.add(word1[0])
if len(word2) > 1:
leading.add(word2[0])
if len(result) > 1:
leading.add(result[0])
mapping: dict[str, int] = {}
used = [False] * 10
def word_to_num(word: str) -> int:
num = 0
for c in word:
num = num * 10 + mapping[c]
return num
def is_valid() -> bool:
return word_to_num(word1) + word_to_num(word2) == word_to_num(result)
def solve(idx: int) -> bool:
if idx == len(letters):
return is_valid()
ch = letters[idx]
for digit in range(10):
if used[digit]:
continue
if digit == 0 and ch in leading:
continue
mapping[ch] = digit
used[digit] = True
if solve(idx + 1):
return True
used[digit] = False
del mapping[ch]
return False
if solve(0):
return mapping
return {}
Rust
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn solve_puzzle(word1: String, word2: String, result: String) -> HashMap<char, i32> {
let all_chars: String = format!("{}{}{}", word1, word2, result);
let unique_chars: HashSet<char> = all_chars.chars().collect();
let letters: Vec<char> = unique_chars.into_iter().collect();
let mut leading = HashSet::new();
if word1.len() > 1 {
leading.insert(word1.chars().next().unwrap());
}
if word2.len() > 1 {
leading.insert(word2.chars().next().unwrap());
}
if result.len() > 1 {
leading.insert(result.chars().next().unwrap());
}
let mut mapping = HashMap::new();
let mut used = vec![false; 10];
fn word_to_num(word: &str, mapping: &HashMap<char, i32>) -> i64 {
word.chars().fold(0, |acc, c| acc * 10 + mapping[&c] as i64)
}
fn is_valid(word1: &str, word2: &str, result: &str, mapping: &HashMap<char, i32>) -> bool {
word_to_num(word1, mapping) + word_to_num(word2, mapping) == word_to_num(result, mapping)
}
fn solve(
idx: usize,
letters: &[char],
leading: &HashSet<char>,
word1: &str,
word2: &str,
result: &str,
mapping: &mut HashMap<char, i32>,
used: &mut Vec<bool>
) -> bool {
if idx == letters.len() {
return is_valid(word1, word2, result, mapping);
}
let ch = letters[idx];
for digit in 0..=9 {
if used[digit as usize] {
continue;
}
if digit == 0 && leading.contains(&ch) {
continue;
}
mapping.insert(ch, digit);
used[digit as usize] = true;
if solve(idx + 1, letters, leading, word1, word2, result, mapping, used) {
return true;
}
used[digit as usize] = false;
mapping.remove(&ch);
}
false
}
if solve(0, &letters, &leading, &word1, &word2, &result, &mut mapping, &mut used) {
mapping
} else {
HashMap::new()
}
}
}
TypeScript
class Solution {
private letters: string[] = [];
private leading: Set<string> = new Set();
private mapping: Map<string, number> = new Map();
private used: boolean[] = new Array(10).fill(false);
private w1: string = '';
private w2: string = '';
private res: string = '';
private wordToNum(word: string): number {
let num = 0;
for (const c of word) {
num = num * 10 + this.mapping.get(c)!;
}
return num;
}
private isValid(): boolean {
return this.wordToNum(this.w1) + this.wordToNum(this.w2) === this.wordToNum(this.res);
}
private solve(idx: number): boolean {
if (idx === this.letters.length) {
return this.isValid();
}
const ch = this.letters[idx];
for (let digit = 0; digit <= 9; digit++) {
if (this.used[digit]) continue;
if (digit === 0 && this.leading.has(ch)) continue;
this.mapping.set(ch, digit);
this.used[digit] = true;
if (this.solve(idx + 1)) return true;
this.used[digit] = false;
this.mapping.delete(ch);
}
return false;
}
solvePuzzle(word1: string, word2: string, result: string): Map<string, number> {
this.w1 = word1;
this.w2 = word2;
this.res = result;
const unique = new Set([...word1, ...word2, ...result]);
this.letters = Array.from(unique);
this.leading.clear();
if (word1.length > 1) this.leading.add(word1[0]);
if (word2.length > 1) this.leading.add(word2[0]);
if (result.length > 1) this.leading.add(result[0]);
this.mapping.clear();
this.used.fill(false);
return this.solve(0) ? new Map(this.mapping) : new Map();
}
}
Complexity
- ⏰ Time complexity:
O(10!), where we have at most 10 unique letters and try all possible permutations of digits 0-9 in the worst case. In practice, pruning makes it much faster. - 🧺 Space complexity:
O(n), where n is the number of unique letters, for storing the mapping and recursion stack.
Method 2 – Optimized Backtracking with Early Pruning
Advanced Intuition
We can optimize the basic backtracking approach by implementing more aggressive pruning strategies. Instead of waiting until all letters are assigned to check validity, we can validate partial solutions and prune invalid branches early.
Enhanced Approach
- Order letters by frequency or constraints to reduce search space
- Implement carry-aware validation that checks partial arithmetic constraints
- Use column-wise validation starting from the rightmost column
- Early termination when partial sums indicate impossible solutions
- Constraint propagation to eliminate invalid digit choices
Code
C++
class Solution {
private:
vector<char> letters;
unordered_map<char, int> mapping;
vector<bool> used;
string w1, w2, res;
bool canFormResult(int col, int carry) {
if (col < 0) return carry == 0;
int sum = carry;
if (col < w1.length()) {
char c1 = w1[w1.length() - 1 - col];
if (mapping.find(c1) == mapping.end()) return true;
sum += mapping[c1];
}
if (col < w2.length()) {
char c2 = w2[w2.length() - 1 - col];
if (mapping.find(c2) == mapping.end()) return true;
sum += mapping[c2];
}
if (col < res.length()) {
char cr = res[res.length() - 1 - col];
if (mapping.find(cr) == mapping.end()) return true;
int expected = mapping[cr];
return sum % 10 == expected;
}
return sum < 10;
}
bool solve(int idx) {
// Check partial constraint satisfaction
for (int col = 0; col < max({w1.length(), w2.length(), res.length()}); col++) {
int carry = 0;
for (int c = 0; c <= col; c++) {
if (!canFormResult(c, carry)) return false;
// Calculate carry for next iteration
int sum = carry;
if (c < w1.length()) {
char c1 = w1[w1.length() - 1 - c];
if (mapping.find(c1) != mapping.end()) sum += mapping[c1];
}
if (c < w2.length()) {
char c2 = w2[w2.length() - 1 - c];
if (mapping.find(c2) != mapping.end()) sum += mapping[c2];
}
carry = sum / 10;
}
}
if (idx == letters.size()) {
long long num1 = 0, num2 = 0, numRes = 0;
for (char c : w1) num1 = num1 * 10 + mapping[c];
for (char c : w2) num2 = num2 * 10 + mapping[c];
for (char c : res) numRes = numRes * 10 + mapping[c];
return num1 + num2 == numRes;
}
char ch = letters[idx];
for (int digit = 0; digit <= 9; digit++) {
if (used[digit]) continue;
if (digit == 0 && ((w1.length() > 1 && w1[0] == ch) ||
(w2.length() > 1 && w2[0] == ch) ||
(res.length() > 1 && res[0] == ch))) continue;
mapping[ch] = digit;
used[digit] = true;
if (solve(idx + 1)) return true;
used[digit] = false;
mapping.erase(ch);
}
return false;
}
public:
unordered_map<char, int> solvePuzzleOptimized(string word1, string word2, string result) {
w1 = word1; w2 = word2; res = result;
unordered_set<char> unique;
for (char c : word1 + word2 + result) {
unique.insert(c);
}
for (char c : unique) {
letters.push_back(c);
}
used.resize(10, false);
if (solve(0)) return mapping;
return {};
}
};
Go
func solvePuzzleOptimized(word1, word2, result string) map[rune]int {
allChars := word1 + word2 + result
unique := make(map[rune]bool)
for _, c := range allChars {
unique[c] = true
}
var letters []rune
for c := range unique {
letters = append(letters, c)
}
mapping := make(map[rune]int)
used := make([]bool, 10)
var validatePartial func() bool
validatePartial = func() bool {
maxLen := len(word1)
if len(word2) > maxLen {
maxLen = len(word2)
}
if len(result) > maxLen {
maxLen = len(result)
}
carry := 0
for pos := 0; pos < maxLen; pos++ {
colSum := carry
if pos < len(word1) {
c1 := rune(word1[len(word1)-1-pos])
if val, ok := mapping[c1]; ok {
colSum += val
}
}
if pos < len(word2) {
c2 := rune(word2[len(word2)-1-pos])
if val, ok := mapping[c2]; ok {
colSum += val
}
}
if pos < len(result) {
cr := rune(result[len(result)-1-pos])
if expected, ok := mapping[cr]; ok {
if colSum%10 != expected {
return false
}
}
}
carry = colSum / 10
}
return true
}
var solve func(int) bool
solve = func(idx int) bool {
if !validatePartial() {
return false
}
if idx == len(letters) {
return wordToNumOptimized(word1, mapping) + wordToNumOptimized(word2, mapping) == wordToNumOptimized(result, mapping)
}
ch := letters[idx]
for digit := 0; digit <= 9; digit++ {
if used[digit] {
continue
}
if digit == 0 && (
(len(word1) > 1 && rune(word1[0]) == ch) ||
(len(word2) > 1 && rune(word2[0]) == ch) ||
(len(result) > 1 && rune(result[0]) == ch)) {
continue
}
mapping[ch] = digit
used[digit] = true
if solve(idx + 1) {
return true
}
used[digit] = false
delete(mapping, ch)
}
return false
}
if solve(0) {
return mapping
}
return make(map[rune]int)
}
func wordToNumOptimized(word string, mapping map[rune]int) int64 {
var num int64
for _, c := range word {
num = num*10 + int64(mapping[c])
}
return num
}
Java
class Solution {
private List<Character> letters;
private Map<Character, Integer> mapping;
private boolean[] used;
private String w1, w2, res;
private boolean validatePartial() {
int maxLen = Math.max(Math.max(w1.length(), w2.length()), res.length());
int carry = 0;
for (int pos = 0; pos < maxLen; pos++) {
int colSum = carry;
if (pos < w1.length()) {
char c1 = w1.charAt(w1.length() - 1 - pos);
if (mapping.containsKey(c1)) {
colSum += mapping.get(c1);
}
}
if (pos < w2.length()) {
char c2 = w2.charAt(w2.length() - 1 - pos);
if (mapping.containsKey(c2)) {
colSum += mapping.get(c2);
}
}
if (pos < res.length()) {
char cr = res.charAt(res.length() - 1 - pos);
if (mapping.containsKey(cr)) {
int expected = mapping.get(cr);
if (colSum % 10 != expected) {
return false;
}
}
}
carry = colSum / 10;
}
return true;
}
private boolean solve(int idx) {
if (!validatePartial()) return false;
if (idx == letters.size()) {
long num1 = 0, num2 = 0, numRes = 0;
for (char c : w1.toCharArray()) num1 = num1 * 10 + mapping.get(c);
for (char c : w2.toCharArray()) num2 = num2 * 10 + mapping.get(c);
for (char c : res.toCharArray()) numRes = numRes * 10 + mapping.get(c);
return num1 + num2 == numRes;
}
char ch = letters.get(idx);
for (int digit = 0; digit <= 9; digit++) {
if (used[digit]) continue;
if (digit == 0 && ((w1.length() > 1 && w1.charAt(0) == ch) ||
(w2.length() > 1 && w2.charAt(0) == ch) ||
(res.length() > 1 && res.charAt(0) == ch))) continue;
mapping.put(ch, digit);
used[digit] = true;
if (solve(idx + 1)) return true;
used[digit] = false;
mapping.remove(ch);
}
return false;
}
public Map<Character, Integer> solvePuzzleOptimized(String word1, String word2, String result) {
w1 = word1; w2 = word2; res = result;
Set<Character> unique = new HashSet<>();
for (char c : (word1 + word2 + result).toCharArray()) {
unique.add(c);
}
letters = new ArrayList<>(unique);
mapping = new HashMap<>();
used = new boolean[10];
if (solve(0)) return new HashMap<>(mapping);
return new HashMap<>();
}
}
Kotlin
class Solution {
private lateinit var letters: List<Char>
private val mapping = mutableMapOf<Char, Int>()
private val used = BooleanArray(10)
private lateinit var w1: String
private lateinit var w2: String
private lateinit var res: String
private fun validatePartial(): Boolean {
val maxLen = maxOf(w1.length, w2.length, res.length)
var carry = 0
for (pos in 0 until maxLen) {
var colSum = carry
if (pos < w1.length) {
val c1 = w1[w1.length - 1 - pos]
if (c1 in mapping) {
colSum += mapping[c1]!!
}
}
if (pos < w2.length) {
val c2 = w2[w2.length - 1 - pos]
if (c2 in mapping) {
colSum += mapping[c2]!!
}
}
if (pos < res.length) {
val cr = res[res.length - 1 - pos]
if (cr in mapping) {
val expected = mapping[cr]!!
if (colSum % 10 != expected) {
return false
}
}
}
carry = colSum / 10
}
return true
}
private fun solve(idx: Int): Boolean {
if (!validatePartial()) return false
if (idx == letters.size) {
val num1 = w1.fold(0L) { acc, c -> acc * 10 + mapping[c]!! }
val num2 = w2.fold(0L) { acc, c -> acc * 10 + mapping[c]!! }
val numRes = res.fold(0L) { acc, c -> acc * 10 + mapping[c]!! }
return num1 + num2 == numRes
}
val ch = letters[idx]
for (digit in 0..9) {
if (used[digit]) continue
// Leading zero constraint
if (digit == 0 && (
(w1.length > 1 && ch == w1[0]) ||
(w2.length > 1 && ch == w2[0]) ||
(res.length > 1 && ch == res[0])
)) continue
mapping[ch] = digit
used[digit] = true
if (solve(idx + 1)) return true
used[digit] = false
mapping.remove(ch)
}
return false
}
fun solvePuzzleOptimized(word1: String, word2: String, result: String): Map<Char, Int> {
w1 = word1
w2 = word2
res = result
val unique = (word1 + word2 + result).toSet()
letters = unique.toList()
return if (solve(0)) mapping.toMap() else emptyMap()
}
}
Python
class Solution:
def solvePuzzleOptimized(self, word1: str, word2: str, result: str) -> dict[str, int]:
unique_chars = set(word1 + word2 + result)
letters = list(unique_chars)
# Sort letters by position importance (rightmost first for arithmetic)
letters.sort(key=lambda x: (
-1 if x in {word1[-1], word2[-1], result[-1]} else 0,
-1 if len(word1) > 1 and x == word1[0] else 0,
-1 if len(word2) > 1 and x == word2[0] else 0,
-1 if len(result) > 1 and x == result[0] else 0
))
mapping: dict[str, int] = {}
used = [False] * 10
def validate_partial() -> bool:
"""Check if current partial assignment can lead to valid solution"""
max_len = max(len(word1), len(word2), len(result))
carry = 0
for pos in range(max_len):
col_sum = carry
# Add digit from word1 if exists and assigned
if pos < len(word1):
c1 = word1[-(pos + 1)]
if c1 in mapping:
col_sum += mapping[c1]
elif pos == len(word1) - 1: # Not assigned yet
return True
# Add digit from word2 if exists and assigned
if pos < len(word2):
c2 = word2[-(pos + 1)]
if c2 in mapping:
col_sum += mapping[c2]
elif pos == len(word2) - 1: # Not assigned yet
return True
# Check result digit if exists and assigned
if pos < len(result):
cr = result[-(pos + 1)]
if cr in mapping:
expected = mapping[cr]
if col_sum % 10 != expected:
return False
else: # Not assigned yet
return True
carry = col_sum // 10
return carry == 0
def solve(idx: int) -> bool:
if not validate_partial():
return False
if idx == len(letters):
num1 = int(''.join(str(mapping[c]) for c in word1))
num2 = int(''.join(str(mapping[c]) for c in word2))
num_res = int(''.join(str(mapping[c]) for c in result))
return num1 + num2 == num_res
ch = letters[idx]
for digit in range(10):
if used[digit]:
continue
# Check leading zero constraint
if digit == 0 and (
(len(word1) > 1 and ch == word1[0]) or
(len(word2) > 1 and ch == word2[0]) or
(len(result) > 1 and ch == result[0])
):
continue
mapping[ch] = digit
used[digit] = True
if solve(idx + 1):
return True
used[digit] = False
del mapping[ch]
return False
if solve(0):
return mapping
return {}
Rust
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn solve_puzzle_optimized(word1: String, word2: String, result: String) -> HashMap<char, i32> {
let all_chars: String = format!("{}{}{}", word1, word2, result);
let unique_chars: HashSet<char> = all_chars.chars().collect();
let letters: Vec<char> = unique_chars.into_iter().collect();
let mut mapping = HashMap::new();
let mut used = vec![false; 10];
fn validate_partial(
word1: &str,
word2: &str,
result: &str,
mapping: &HashMap<char, i32>
) -> bool {
let max_len = word1.len().max(word2.len()).max(result.len());
let mut carry = 0;
for pos in 0..max_len {
let mut col_sum = carry;
if pos < word1.len() {
let c1 = word1.chars().nth(word1.len() - 1 - pos).unwrap();
if let Some(&val) = mapping.get(&c1) {
col_sum += val;
}
}
if pos < word2.len() {
let c2 = word2.chars().nth(word2.len() - 1 - pos).unwrap();
if let Some(&val) = mapping.get(&c2) {
col_sum += val;
}
}
if pos < result.len() {
let cr = result.chars().nth(result.len() - 1 - pos).unwrap();
if let Some(&expected) = mapping.get(&cr) {
if col_sum % 10 != expected {
return false;
}
}
}
carry = col_sum / 10;
}
true
}
fn solve(
idx: usize,
letters: &[char],
word1: &str,
word2: &str,
result: &str,
mapping: &mut HashMap<char, i32>,
used: &mut Vec<bool>
) -> bool {
if !validate_partial(word1, word2, result, mapping) {
return false;
}
if idx == letters.len() {
let num1: i64 = word1.chars()
.map(|c| mapping[&c] as i64)
.fold(0, |acc, d| acc * 10 + d);
let num2: i64 = word2.chars()
.map(|c| mapping[&c] as i64)
.fold(0, |acc, d| acc * 10 + d);
let num_res: i64 = result.chars()
.map(|c| mapping[&c] as i64)
.fold(0, |acc, d| acc * 10 + d);
return num1 + num2 == num_res;
}
let ch = letters[idx];
for digit in 0..=9 {
if used[digit as usize] {
continue;
}
// Leading zero constraint
if digit == 0 && (
(word1.len() > 1 && word1.chars().next().unwrap() == ch) ||
(word2.len() > 1 && word2.chars().next().unwrap() == ch) ||
(result.len() > 1 && result.chars().next().unwrap() == ch)
) {
continue;
}
mapping.insert(ch, digit);
used[digit as usize] = true;
if solve(idx + 1, letters, word1, word2, result, mapping, used) {
return true;
}
used[digit as usize] = false;
mapping.remove(&ch);
}
false
}
if solve(0, &letters, &word1, &word2, &result, &mut mapping, &mut used) {
mapping
} else {
HashMap::new()
}
}
}
TypeScript
class Solution {
private letters: string[] = [];
private mapping: Map<string, number> = new Map();
private used: boolean[] = new Array(10).fill(false);
private w1: string = '';
private w2: string = '';
private res: string = '';
private validatePartial(): boolean {
const maxLen = Math.max(this.w1.length, this.w2.length, this.res.length);
let carry = 0;
for (let pos = 0; pos < maxLen; pos++) {
let colSum = carry;
if (pos < this.w1.length) {
const c1 = this.w1[this.w1.length - 1 - pos];
if (this.mapping.has(c1)) {
colSum += this.mapping.get(c1)!;
}
}
if (pos < this.w2.length) {
const c2 = this.w2[this.w2.length - 1 - pos];
if (this.mapping.has(c2)) {
colSum += this.mapping.get(c2)!;
}
}
if (pos < this.res.length) {
const cr = this.res[this.res.length - 1 - pos];
if (this.mapping.has(cr)) {
const expected = this.mapping.get(cr)!;
if (colSum % 10 !== expected) {
return false;
}
}
}
carry = Math.floor(colSum / 10);
}
return true;
}
private solve(idx: number): boolean {
if (!this.validatePartial()) return false;
if (idx === this.letters.length) {
const num1 = parseInt(this.w1.split('').map(c => this.mapping.get(c)!).join(''));
const num2 = parseInt(this.w2.split('').map(c => this.mapping.get(c)!).join(''));
const numRes = parseInt(this.res.split('').map(c => this.mapping.get(c)!).join(''));
return num1 + num2 === numRes;
}
const ch = this.letters[idx];
for (let digit = 0; digit <= 9; digit++) {
if (this.used[digit]) continue;
// Leading zero constraint
if (digit === 0 && (
(this.w1.length > 1 && ch === this.w1[0]) ||
(this.w2.length > 1 && ch === this.w2[0]) ||
(this.res.length > 1 && ch === this.res[0])
)) continue;
this.mapping.set(ch, digit);
this.used[digit] = true;
if (this.solve(idx + 1)) return true;
this.used[digit] = false;
this.mapping.delete(ch);
}
return false;
}
solvePuzzleOptimized(word1: string, word2: string, result: string): Map<string, number> {
this.w1 = word1;
this.w2 = word2;
this.res = result;
const unique = new Set([...word1, ...word2, ...result]);
this.letters = Array.from(unique);
this.mapping.clear();
this.used.fill(false);
return this.solve(0) ? new Map(this.mapping) : new Map();
}
}
Optimized Complexity
- ⏰ Time complexity:
O(10!)in worst case, but significantly faster in practice due to early pruning and constraint propagation - 🧺 Space complexity:
O(n), where n is the number of unique letters, for mapping and recursion stack