Facebook Pixel

1307. Verbal Arithmetic Puzzle

HardArrayMathStringBacktracking
Leetcode Link

Problem Description

This problem asks you to determine if a cryptarithmetic equation can be solved. You're given a list of words that represent the left side of an addition equation, and a result word that represents the right side. Each letter in these words must be mapped to a unique digit (0-9) such that when the words are treated as numbers and added together, they equal the result.

The key constraints are:

  1. Each letter maps to exactly one digit (0-9): Once you assign a digit to a letter, that letter always represents that same digit throughout the equation.

  2. No two letters can map to the same digit: Each letter must have a unique digit assignment.

  3. No leading zeros: Numbers cannot have leading zeros, except for single-digit numbers. For example, if a word has multiple characters, its first character cannot map to 0.

  4. The equation must be valid: When you replace all letters with their assigned digits and perform the addition, the sum of the words on the left must equal the result on the right.

For example:

  • If words = ["SEND", "MORE"] and result = "MONEY"
  • One valid mapping could be: S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2
  • This gives us: 9567 + 1085 = 10652, which is correct

The function should return true if at least one valid digit assignment exists that makes the equation work, and false otherwise.

The solution uses a backtracking approach that processes the equation column by column (like manual addition), trying different digit assignments for each letter and checking if the carry operations work correctly throughout the addition.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • No: The problem doesn't involve nodes and edges or graph traversal. It's about assigning digits to letters in an arithmetic equation.

Need to solve for kth smallest/largest?

  • No: We're not looking for any kth smallest or largest element. We need to find if a valid digit mapping exists.

Involves Linked Lists?

  • No: The problem works with strings/words and digit mappings, not linked list data structures.

Does the problem have small constraints?

  • Yes: The constraints are relatively small:
    • We only have 10 possible digits (0-9) to assign
    • Each letter can only map to one digit
    • The number of unique letters is limited (at most 10 since we only have 10 digits)
    • We need to try different combinations of digit assignments

Brute force / Backtracking?

  • Yes: This is a perfect fit for backtracking because:
    • We need to explore different digit assignments for each letter
    • We can make a choice (assign a digit to a letter), explore if it leads to a solution
    • If it doesn't work, we backtrack and try a different assignment
    • We need to satisfy multiple constraints (no duplicate mappings, no leading zeros, valid arithmetic)

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This problem requires systematically trying different digit-to-letter mappings, validating constraints at each step, and backtracking when we hit an invalid state - which is exactly what the provided solution implements.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Think about how you would solve a cryptarithmetic puzzle by hand. You'd try different digit assignments for letters, checking if they satisfy the equation. When you hit a contradiction, you'd erase your work and try different assignments. This is exactly backtracking.

The key insight is to process the addition column by column, just like manual addition works - from right to left with carries. Why? Because this allows us to fail fast. If the rightmost column doesn't add up correctly with our current letter-to-digit mappings, we know immediately that this path won't work and can backtrack early.

Consider the equation SEND + MORE = MONEY. When adding manually:

    S E N D
  + M O R E
  ---------
  M O N E Y

We start from the rightmost column: D + E = Y (or Y + 10 if there's a carry). If our current digit assignments for D and E don't produce the correct digit for Y (considering any carry), we can immediately reject this path without checking the entire equation.

The solution cleverly traverses the problem in a 2D manner:

  • Columns represent digit positions (ones, tens, hundreds, etc.)
  • Rows represent different words in the equation

For each position, we:

  1. Try to assign digits to unmapped letters
  2. Check if the column sum is valid (considering carries)
  3. If valid, move to the next position; if not, backtrack

The balance (bal) variable tracks the running sum as we process each column. When we finish a column, we check if bal % 10 equals 0 (meaning the column adds up correctly), and carry forward bal // 10 to the next column.

The leading zero constraint is handled by checking the position - if we're at the leftmost digit of a multi-character word, we can't assign 0 to it.

This approach is efficient because it prunes the search space early. Instead of generating all possible complete mappings and then checking the equation (which would be factorial in complexity), we validate incrementally and abandon invalid paths as soon as possible.

Learn more about Math and Backtracking patterns.

Solution Approach

The implementation uses a recursive backtracking function isAnyMapping that processes the equation systematically. Here's how the solution works:

Data Structures:

  • letToDig: HashMap storing letter → digit mappings
  • digToLet: Array storing digit → letter mappings (using "-" for unmapped digits)
  • bal: Running balance to track the column sum with carries

Main Algorithm Flow:

  1. Setup Phase:

    • Append the result word to the words list (treating it as the last word with negative sign)
    • Find totalCols (length of longest word) and totalRows (number of words including result)
    • Initialize empty mappings

  2. Recursive Processing (isAnyMapping):

    The function processes position by position using (row, col) coordinates:

    Base Cases:

    • If col == totalCols: All columns processed, return bal == 0 (no remaining carry)
    • If row == totalRows: Column complete, check if bal % 10 == 0 and recurse to next column with carry bal // 10

  3. Processing Each Position:

    For current word at position (row, col):

    • Skip if word is shorter than current column: col >= len(w)
    • Extract letter from right to left: letter = w[len(w) - 1 - col]
    • Determine sign: positive for addends, negative for result (last word)

  4. Letter-to-Digit Assignment:

    Case 1: Letter already mapped

    • Validate no leading zeros: Check if digit is 0 and position is leftmost in multi-character word
    • If valid, continue with existing mapping and update balance

    Case 2: Letter needs mapping

    • Try each digit 0-9: 
      for i in range(10):
    if digToLet[i] == "-":  # Digit not yet assigned
    • Check leading zero constraint: i != 0 or single character word or not leftmost position
    • Assign mapping: digToLet[i] = letter, letToDig[letter] = i
    • Recursively check if this leads to solution
    • Backtrack if unsuccessful: Remove mappings and try next digit

  5. Balance Tracking:

    The bal variable accumulates the weighted sum for each column:

    • Add digit value for addend words: bal + sign * letToDig[letter]
    • Subtract digit value for result word: bal - letToDig[letter]
    • When column completes, bal % 10 should be 0, and bal // 10 becomes carry

  6. Pruning Strategy:

    The column-by-column approach enables early termination:

    • If a column doesn't balance with current mappings, immediately backtrack
    • No need to complete entire mapping before validation
    • Significantly reduces search space from O(10!) to practical time

The algorithm elegantly combines the manual addition process with backtracking search, validating constraints incrementally rather than generating complete mappings upfront.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's trace through a simple example: words = ["AB", "CD"] and result = "EF"

We need to find digit mappings such that AB + CD = EF.

Setup:

  • Append result to words: ["AB", "CD", "EF"]
  • totalCols = 2 (max word length)
  • totalRows = 3 (number of words)
  • Initialize empty mappings

Processing (row, col) positions:

Start at (0, 0) - rightmost column, first word:

    A B
  + C D
  -----
    E F
    ↑

Column 0 (ones place):

  1. (0, 0): Word "AB", position 0 → letter 'B'

    • B unmapped, try digits 0-9
    • Let's try B=5: bal = 0 + 5 = 5

  2. (1, 0): Word "CD", position 0 → letter 'D'

    • D unmapped, try digits (except 5)
    • Let's try D=7: bal = 5 + 7 = 12

  3. (2, 0): Word "EF", position 0 → letter 'F'

    • F unmapped, need F such that (12 - F) % 10 = 0
    • F must be 2: bal = 12 - 2 = 10

  4. (3, 0): Row complete, check column

    • bal % 10 = 0 ✓ (column balances)
    • Move to column 1 with carry: bal = 10 // 10 = 1

Column 1 (tens place):

    A B
  + C D
  -----
    E F
  ↑

  1. (0, 1): Word "AB", position 1 → letter 'A'

    • A unmapped, can't be 0 (leading digit)
    • Try A=3: bal = 1 + 3 = 4

  2. (1, 1): Word "CD", position 1 → letter 'C'

    • C unmapped, can't be 0 (leading digit)
    • Try C=4: bal = 4 + 4 = 8

  3. (2, 1): Word "EF", position 1 → letter 'E'

    • E unmapped, can't be 0 (leading digit)
    • Need E such that (8 - E) % 10 = 0
    • E must be 8: bal = 8 - 8 = 0

  4. (3, 1): Row complete

    • bal % 10 = 0 ✓
    • Move to column 2 with carry: bal = 0

  5. (0, 2): col == totalCols

    • All columns processed
    • bal == 0 ✓ (no remaining carry)
    • Success!

Valid mapping found:

  • A=3, B=5, C=4, D=7, E=8, F=2
  • Verification: 35 + 47 = 82 ✓

If at any point a column didn't balance (e.g., if we had tried A=1 instead, giving us 15 + 47 = 62, but E can't be both 6 and 8), we would backtrack and try different digit assignments. The algorithm continues until finding a valid mapping or exhausting all possibilities.

Solution Implementation

1class Solution:
2    def isAnyMapping(
3        self, words, row, col, balance, letter_to_digit, digit_to_letter, total_rows, total_cols
4    ):
5        """
6        Recursively check if there exists a valid digit mapping for the cryptarithmetic equation.
7      
8        Args:
9            words: List of words including the result word at the end
10            row: Current row (word) being processed
11            col: Current column (digit position from right) being processed
12            balance: Running sum/balance for the current column
13            letter_to_digit: Dictionary mapping letters to their assigned digits
14            digit_to_letter: List mapping digits to their assigned letters
15            total_rows: Total number of words
16            total_cols: Maximum length among all words
17      
18        Returns:
19            True if a valid mapping exists, False otherwise
20        """
21        # Base case: Processed all columns successfully
22        if col == total_cols:
23            return balance == 0
24
25        # Finished processing current column, move to next column
26        if row == total_rows:
27            # Check if current column sums to 0 (mod 10) and propagate carry
28            return balance % 10 == 0 and self.isAnyMapping(
29                words, 0, col + 1, balance // 10, letter_to_digit, digit_to_letter, total_rows, total_cols
30            )
31
32        current_word = words[row]
33
34        # Skip if current word doesn't have a character at this column position
35        if col >= len(current_word):
36            return self.isAnyMapping(
37                words, row + 1, col, balance, letter_to_digit, digit_to_letter, total_rows, total_cols
38            )
39
40        # Get the letter at current position (counting from right)
41        letter = current_word[len(current_word) - 1 - col]
42
43        # Determine sign: positive for addends, negative for result (last word)
44        sign = 1 if row < total_rows - 1 else -1
45
46        # Case 1: Letter already has a digit mapping
47        if letter in letter_to_digit:
48            digit = letter_to_digit[letter]
49          
50            # Check for leading zero constraint
51            is_leading_position = (col == len(current_word) - 1)
52            is_single_char_word = (len(current_word) == 1)
53          
54            # Leading zeros are only allowed for single-character words
55            if digit != 0 or is_single_char_word or not is_leading_position:
56                return self.isAnyMapping(
57                    words,
58                    row + 1,
59                    col,
60                    balance + sign * digit,
61                    letter_to_digit,
62                    digit_to_letter,
63                    total_rows,
64                    total_cols,
65                )
66            else:
67                return False
68
69        # Case 2: Letter needs a new digit mapping
70        else:
71            # Try each available digit
72            for digit in range(10):
73                # Check if digit is available
74                if digit_to_letter[digit] == "-":
75                    # Check leading zero constraint
76                    is_leading_position = (col == len(current_word) - 1)
77                    is_single_char_word = (len(current_word) == 1)
78                  
79                    # Skip if this would create an invalid leading zero
80                    if digit == 0 and is_leading_position and not is_single_char_word:
81                        continue
82                  
83                    # Make the assignment
84                    digit_to_letter[digit] = letter
85                    letter_to_digit[letter] = digit
86
87                    # Recursively check if this assignment works
88                    if self.isAnyMapping(
89                        words,
90                        row + 1,
91                        col,
92                        balance + sign * digit,
93                        letter_to_digit,
94                        digit_to_letter,
95                        total_rows,
96                        total_cols,
97                    ):
98                        return True
99
100                    # Backtrack: undo the assignment
101                    digit_to_letter[digit] = "-"
102                    if letter in letter_to_digit:
103                        del letter_to_digit[letter]
104
105        # No valid mapping found
106        return False
107
108    def isSolvable(self, words, result):
109        """
110        Check if the cryptarithmetic equation has a valid solution.
111      
112        Args:
113            words: List of addend words
114            result: The result word
115      
116        Returns:
117            True if equation is solvable, False otherwise
118        """
119        # Combine all words into a single list (result goes last)
120        all_words = words + [result]
121
122        # Count total words and find maximum word length
123        total_rows = len(all_words)
124        total_cols = max(len(word) for word in all_words)
125
126        # Initialize mapping structures
127        letter_to_digit = {}  # Maps each letter to its assigned digit
128        digit_to_letter = ["-"] * 10  # Maps each digit to its assigned letter ("-" means unassigned)
129
130        # Start the recursive search
131        return self.isAnyMapping(
132            all_words, 0, 0, 0, letter_to_digit, digit_to_letter, total_rows, total_cols
133        )
134
1class Solution {
2    /**
3     * Recursive backtracking function to find if there exists a valid digit mapping
4     * for the cryptarithmetic puzzle.
5     * 
6     * @param words List containing all addend words plus the result word
7     * @param row Current row (word) being processed
8     * @param col Current column (digit position from right) being processed
9     * @param balance Running sum/balance for current column
10     * @param letterToDigit HashMap mapping letters to their assigned digits
11     * @param digitToLetter Array mapping digits to their assigned letters
12     * @param totalRows Total number of words (including result)
13     * @param totalCols Maximum word length (number of columns to process)
14     * @return true if a valid mapping exists, false otherwise
15     */
16    private boolean isAnyMapping(List<String> words, int row, int col, int balance,
17            HashMap<Character, Integer> letterToDigit, char[] digitToLetter, 
18            int totalRows, int totalCols) {
19      
20        // Base case: processed all columns
21        if (col == totalCols) {
22            return balance == 0;
23        }
24
25        // Finished processing current column
26        if (row == totalRows) {
27            // Check if current column sums correctly (remainder should be 0)
28            // Move to next column with carry
29            return (balance % 10 == 0 && 
30                    isAnyMapping(words, 0, col + 1, balance / 10, 
31                                letterToDigit, digitToLetter, totalRows, totalCols));
32        }
33
34        String currentWord = words.get(row);
35
36        // Current word doesn't have a character at this column position
37        if (col >= currentWord.length()) {
38            return isAnyMapping(words, row + 1, col, balance, 
39                              letterToDigit, digitToLetter, totalRows, totalCols);
40        }
41
42        // Get character at current position (counting from right)
43        char currentLetter = currentWord.charAt(currentWord.length() - 1 - col);
44
45        // Determine if we add (for addends) or subtract (for result)
46        int sign = (row < totalRows - 1) ? 1 : -1;
47
48        // Case 1: Letter already has a mapping
49        if (letterToDigit.containsKey(currentLetter)) {
50            int digit = letterToDigit.get(currentLetter);
51          
52            // Check for leading zero constraint
53            boolean isValidMapping = (digit != 0) || 
54                                    (digit == 0 && currentWord.length() == 1) || 
55                                    (col != currentWord.length() - 1);
56          
57            if (isValidMapping) {
58                return isAnyMapping(words, row + 1, col, balance + sign * digit,
59                                  letterToDigit, digitToLetter, totalRows, totalCols);
60            }
61        } else {
62            // Case 2: Letter needs a new mapping - try all available digits
63            for (int digit = 0; digit < 10; digit++) {
64                // Check if digit is available
65                if (digitToLetter[digit] == '-') {
66                    // Check for leading zero constraint
67                    boolean isValidDigit = (digit != 0) || 
68                                          (digit == 0 && currentWord.length() == 1) || 
69                                          (col != currentWord.length() - 1);
70                  
71                    if (isValidDigit) {
72                        // Assign mapping
73                        digitToLetter[digit] = currentLetter;
74                        letterToDigit.put(currentLetter, digit);
75
76                        // Recursively check with new mapping
77                        if (isAnyMapping(words, row + 1, col, balance + sign * digit,
78                                       letterToDigit, digitToLetter, totalRows, totalCols)) {
79                            return true;
80                        }
81
82                        // Backtrack: remove mapping
83                        digitToLetter[digit] = '-';
84                        letterToDigit.remove(currentLetter);
85                    }
86                }
87            }
88        }
89
90        // No valid mapping found
91        return false;
92    }
93
94    /**
95     * Determines if the cryptarithmetic equation is solvable.
96     * 
97     * @param wordsArr Array of addend words
98     * @param result The result word
99     * @return true if equation has a valid solution, false otherwise
100     */
101    public boolean isSolvable(String[] wordsArr, String result) {
102        // Combine all addends and result into single list
103        List<String> words = new ArrayList<>();
104        for (String word : wordsArr) {
105            words.add(word);
106        }
107        words.add(result);
108
109        int totalRows = words.size();
110
111        // Find maximum word length (determines number of columns)
112        int totalCols = 0;
113        for (String word : words) {
114            totalCols = Math.max(totalCols, word.length());
115        }
116
117        // Initialize letter-to-digit mapping
118        HashMap<Character, Integer> letterToDigit = new HashMap<>();
119
120        // Initialize digit-to-letter mapping (using '-' for unassigned)
121        char[] digitToLetter = new char[10];
122        for (int i = 0; i < 10; i++) {
123            digitToLetter[i] = '-';
124        }
125
126        // Start backtracking from row 0, column 0, with balance 0
127        return isAnyMapping(words, 0, 0, 0, letterToDigit, digitToLetter, 
128                          totalRows, totalCols);
129    }
130}
131
1class Solution {
2public:
3    /**
4     * Recursive backtracking function to find valid digit mappings for letters
5     * @param words: vector of words including the result word at the end
6     * @param row: current row (word) being processed
7     * @param col: current column (digit position from right) being processed
8     * @param balance: running sum/balance to check equation validity
9     * @param letterToDigit: mapping from letters to digits
10     * @param digitToLetter: mapping from digits to letters
11     * @param totalRows: total number of words (including result)
12     * @param totalCols: maximum word length
13     * @return: true if valid mapping exists, false otherwise
14     */
15    bool isAnyMapping(vector<string>& words, int row, int col, int balance, 
16                      unordered_map<char, int>& letterToDigit,
17                      vector<char>& digitToLetter, int totalRows, int totalCols) {
18      
19        // Base case: processed all columns, check if equation balances to zero
20        if (col == totalCols) {
21            return balance == 0;
22        }
23
24        // Finished processing current column, move to next column with carry
25        if (row == totalRows) {
26            return (balance % 10 == 0) && 
27                   isAnyMapping(words, 0, col + 1, balance / 10, 
28                               letterToDigit, digitToLetter, totalRows, totalCols);
29        }
30
31        string currentWord = words[row];
32
33        // Skip if current word doesn't have a character at this column position
34        if (col >= currentWord.length()) {
35            return isAnyMapping(words, row + 1, col, balance, 
36                               letterToDigit, digitToLetter, totalRows, totalCols);
37        }
38
39        // Get character at current position (counting from right)
40        char currentLetter = currentWord[currentWord.length() - 1 - col];
41
42        // Determine sign: positive for addends, negative for result (last word)
43        int sign = (row < totalRows - 1) ? 1 : -1;
44
45        // Case 1: Letter already has a digit mapping
46        if (letterToDigit.count(currentLetter)) {
47            int digit = letterToDigit[currentLetter];
48          
49            // Check for leading zero constraint
50            bool isValidMapping = (digit != 0) || 
51                                 (digit == 0 && currentWord.length() == 1) || 
52                                 (col != currentWord.length() - 1);
53          
54            if (isValidMapping) {
55                return isAnyMapping(words, row + 1, col, balance + sign * digit,
56                                   letterToDigit, digitToLetter, totalRows, totalCols);
57            }
58            return false;
59        }
60      
61        // Case 2: Letter needs a new digit mapping
62        for (int digit = 0; digit < 10; digit++) {
63            // Check if digit is available and satisfies leading zero constraint
64            bool isDigitAvailable = (digitToLetter[digit] == '-');
65            bool satisfiesLeadingZeroRule = (digit != 0) || 
66                                           (digit == 0 && currentWord.length() == 1) || 
67                                           (col != currentWord.length() - 1);
68          
69            if (isDigitAvailable && satisfiesLeadingZeroRule) {
70                // Apply mapping
71                digitToLetter[digit] = currentLetter;
72                letterToDigit[currentLetter] = digit;
73
74                // Recursively check with new mapping
75                bool foundSolution = isAnyMapping(words, row + 1, col, 
76                                                 balance + sign * digit,
77                                                 letterToDigit, digitToLetter, 
78                                                 totalRows, totalCols);
79
80                if (foundSolution) {
81                    return true;
82                }
83
84                // Backtrack: remove mapping
85                digitToLetter[digit] = '-';
86                letterToDigit.erase(currentLetter);
87            }
88        }
89
90        // No valid mapping found
91        return false;
92    }
93
94    /**
95     * Main function to check if the cryptarithmetic equation is solvable
96     * @param words: vector of addend words
97     * @param result: result word
98     * @return: true if equation has a valid solution, false otherwise
99     */
100    bool isSolvable(vector<string>& words, string result) {
101        // Append result to words vector for unified processing
102        words.push_back(result);
103
104        // Calculate dimensions for processing
105        int totalRows = words.size();
106        int totalCols = 0;
107      
108        // Find maximum word length
109        for (const string& word : words) {
110            totalCols = max(totalCols, static_cast<int>(word.size()));
111        }
112
113        // Initialize mapping data structures
114        unordered_map<char, int> letterToDigit;  // Maps each letter to its digit
115        vector<char> digitToLetter(10, '-');     // Maps each digit to its letter ('-' means unassigned)
116
117        // Start recursive backtracking from position (0, 0) with balance 0
118        return isAnyMapping(words, 0, 0, 0, letterToDigit, digitToLetter, 
119                           totalRows, totalCols);
120    }
121};
122
1/**
2 * Recursive backtracking function to find valid digit mappings for letters
3 * @param words - array of words including the result word at the end
4 * @param row - current row (word) being processed
5 * @param col - current column (digit position from right) being processed
6 * @param balance - running sum/balance to check equation validity
7 * @param letterToDigit - mapping from letters to digits
8 * @param digitToLetter - mapping from digits to letters
9 * @param totalRows - total number of words (including result)
10 * @param totalCols - maximum word length
11 * @returns true if valid mapping exists, false otherwise
12 */
13function isAnyMapping(
14    words: string[],
15    row: number,
16    col: number,
17    balance: number,
18    letterToDigit: Map<string, number>,
19    digitToLetter: string[],
20    totalRows: number,
21    totalCols: number
22): boolean {
23    // Base case: processed all columns, check if equation balances to zero
24    if (col === totalCols) {
25        return balance === 0;
26    }
27
28    // Finished processing current column, move to next column with carry
29    if (row === totalRows) {
30        return (balance % 10 === 0) && 
31               isAnyMapping(words, 0, col + 1, Math.floor(balance / 10), 
32                           letterToDigit, digitToLetter, totalRows, totalCols);
33    }
34
35    const currentWord = words[row];
36
37    // Skip if current word doesn't have a character at this column position
38    if (col >= currentWord.length) {
39        return isAnyMapping(words, row + 1, col, balance, 
40                           letterToDigit, digitToLetter, totalRows, totalCols);
41    }
42
43    // Get character at current position (counting from right)
44    const currentLetter = currentWord[currentWord.length - 1 - col];
45
46    // Determine sign: positive for addends, negative for result (last word)
47    const sign = (row < totalRows - 1) ? 1 : -1;
48
49    // Case 1: Letter already has a digit mapping
50    if (letterToDigit.has(currentLetter)) {
51        const digit = letterToDigit.get(currentLetter)!;
52      
53        // Check for leading zero constraint
54        const isValidMapping = (digit !== 0) || 
55                             (digit === 0 && currentWord.length === 1) || 
56                             (col !== currentWord.length - 1);
57      
58        if (isValidMapping) {
59            return isAnyMapping(words, row + 1, col, balance + sign * digit,
60                               letterToDigit, digitToLetter, totalRows, totalCols);
61        }
62        return false;
63    }
64  
65    // Case 2: Letter needs a new digit mapping
66    for (let digit = 0; digit < 10; digit++) {
67        // Check if digit is available and satisfies leading zero constraint
68        const isDigitAvailable = (digitToLetter[digit] === '-');
69        const satisfiesLeadingZeroRule = (digit !== 0) || 
70                                       (digit === 0 && currentWord.length === 1) || 
71                                       (col !== currentWord.length - 1);
72      
73        if (isDigitAvailable && satisfiesLeadingZeroRule) {
74            // Apply mapping
75            digitToLetter[digit] = currentLetter;
76            letterToDigit.set(currentLetter, digit);
77
78            // Recursively check with new mapping
79            const foundSolution = isAnyMapping(words, row + 1, col, 
80                                             balance + sign * digit,
81                                             letterToDigit, digitToLetter, 
82                                             totalRows, totalCols);
83
84            if (foundSolution) {
85                return true;
86            }
87
88            // Backtrack: remove mapping
89            digitToLetter[digit] = '-';
90            letterToDigit.delete(currentLetter);
91        }
92    }
93
94    // No valid mapping found
95    return false;
96}
97
98/**
99 * Main function to check if the cryptarithmetic equation is solvable
100 * @param words - array of addend words
101 * @param result - result word
102 * @returns true if equation has a valid solution, false otherwise
103 */
104function isSolvable(words: string[], result: string): boolean {
105    // Append result to words array for unified processing
106    words.push(result);
107
108    // Calculate dimensions for processing
109    const totalRows = words.length;
110    let totalCols = 0;
111  
112    // Find maximum word length
113    for (const word of words) {
114        totalCols = Math.max(totalCols, word.length);
115    }
116
117    // Initialize mapping data structures
118    const letterToDigit = new Map<string, number>();  // Maps each letter to its digit
119    const digitToLetter = new Array<string>(10).fill('-');  // Maps each digit to its letter ('-' means unassigned)
120
121    // Start recursive backtracking from position (0, 0) with balance 0
122    return isAnyMapping(words, 0, 0, 0, letterToDigit, digitToLetter, 
123                       totalRows, totalCols);
124}
125

Time and Space Complexity

Time Complexity: O(n * 10^m) where n is the total number of characters across all words and m is the number of unique letters.

The algorithm uses backtracking to try all possible digit mappings for each unique letter. In the worst case:

  • We have up to m unique letters that need to be assigned digits
  • For each letter, we try up to 10 different digits (0-9)
  • This gives us 10^m possible combinations to explore
  • For each combination, we traverse through all positions in the grid, which is bounded by O(n) where n is the total number of characters
  • The recursion depth is at most totalRows * totalCols, which is also O(n)

Space Complexity: O(m + n) where m is the number of unique letters and n is the total number of characters.

The space complexity consists of:

  • letToDig HashMap: O(m) for storing letter-to-digit mappings
  • digToLet list: O(10) = O(1) for storing digit-to-letter mappings
  • Recursion call stack: O(totalRows * totalCols) = O(n) in the worst case
  • Input storage for words list: O(n) for storing all characters

Therefore, the total space complexity is O(m + n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Leading Zero Validation

The Pitfall: A common mistake is incorrectly checking for leading zeros. Developers often forget that:

  • Single-character words CAN be 0 (e.g., "A" can map to 0)
  • The leading zero check should only apply to the leftmost character of multi-character words
  • The position check must account for processing from right to left

Incorrect Implementation:

# Wrong: Doesn't allow single-character words to be 0
if digit == 0 and col == len(current_word) - 1:
    return False

# Wrong: Checks position incorrectly
if digit == 0 and col == 0:  # This checks rightmost, not leftmost!
    return False

Correct Implementation:

is_leading_position = (col == len(current_word) - 1)
is_single_char_word = (len(current_word) == 1)

# Only reject if it's a leading zero in a multi-character word
if digit == 0 and is_leading_position and not is_single_char_word:
    continue  # or return False

2. Forgetting to Properly Backtrack

The Pitfall: When trying different digit assignments, it's crucial to completely undo the mapping if it doesn't lead to a solution. Forgetting to remove the letter from the dictionary can cause incorrect results.

Incorrect Implementation:

# Wrong: Only undoing one side of the mapping
digit_to_letter[digit] = letter
letter_to_digit[letter] = digit

if self.isAnyMapping(...):
    return True

digit_to_letter[digit] = "-"  # Forgot to remove from letter_to_digit!

Correct Implementation:

# Make the assignment
digit_to_letter[digit] = letter
letter_to_digit[letter] = digit

if self.isAnyMapping(...):
    return True

# Properly backtrack both mappings
digit_to_letter[digit] = "-"
if letter in letter_to_digit:
    del letter_to_digit[letter]

3. Incorrect Balance/Carry Handling

The Pitfall: The balance accumulation and carry propagation can be confusing. Common errors include:

  • Not resetting balance when moving to a new column
  • Incorrectly handling the sign for the result word
  • Not properly checking if a column sums to 0 (mod 10)

Incorrect Implementation:

# Wrong: Not checking modulo 10 for column validation
if row == total_rows:
    return balance == 0 and self.isAnyMapping(
        words, 0, col + 1, balance, ...)  # Should pass carry, not full balance!

# Wrong: Using same sign for all words
sign = 1  # Should be negative for result word

Correct Implementation:

if row == total_rows:
    # Check column sums to 0 (mod 10) and pass carry to next column
    return balance % 10 == 0 and self.isAnyMapping(
        words, 0, col + 1, balance // 10, ...)

# Correct sign assignment
sign = 1 if row < total_rows - 1 else -1

4. Processing Words in Wrong Direction

The Pitfall: Since addition happens from right to left (units, tens, hundreds...), the column index represents positions from the right. Accessing characters incorrectly will lead to wrong results.

Incorrect Implementation:

# Wrong: Accessing from left
letter = current_word[col]

Correct Implementation:

# Access from right side (index from the end)
letter = current_word[len(current_word) - 1 - col]

5. Not Handling Words of Different Lengths

The Pitfall: Words can have different lengths, and shorter words don't have characters at higher column positions. Failing to skip these positions causes index errors or incorrect processing.

Incorrect Implementation:

# Wrong: Always trying to access character at position
letter = current_word[len(current_word) - 1 - col]  # IndexError if col >= len(word)

Correct Implementation:

# Skip if word doesn't have a character at this column
if col >= len(current_word):
    return self.isAnyMapping(
        words, row + 1, col, balance, ...)

# Now safe to access
letter = current_word[len(current_word) - 1 - col]
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More