Three-Word Additive Cryptarithmetic Solver

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:

1
2
3
4


  SEND
+ MORE
-----
 MONEY

may have the solution:

1

{'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

1
2
3


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

1
2
3


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

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


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 {};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


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<>();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


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()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


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 {}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74


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()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


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

Implementation

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97


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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91


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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89


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

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Solutions#

Method 1 – Backtracking with Constraint Satisfaction#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Optimized Backtracking with Early Pruning#

Advanced Intuition#

Enhanced Approach#

Implementation#

C++#

Go#

Java#

Kotlin#

Python#

Rust#

TypeScript#

Optimized Complexity#