LeetCode Solutions Blog

Verbal Arithmetic Puzzle

Number: 1429

Difficulty: Hard

Paid? No

Problem Description

Given an equation with a list of words on the left side and a result word on the right, assign each unique uppercase letter a unique digit (0-9) so that when the letters are replaced by their corresponding digits the sum of the numbers formed by the words equals the number represented by the result. Ensure that no number has leading zeros.

Key Insights

Identify and extract all unique characters involved (at most 10).
Use backtracking to explore assignments of digits to letters.
Enforce constraints: no duplicate assignments, and ensure that words do not have a leading zero.
Once all letters have been assigned, convert the words and result into numbers to check if their sum matches.
Prune the search space early by checking partial sums if possible.

Space and Time Complexity

Time Complexity: O(10!) in worst-case, since up to 10 letters might need all permutations. Space Complexity: O(10) due to recursive call depth and storing the mapping for up to 10 letters.

Solution

We use a backtracking approach to assign digits to each unique letter. First, extract all unique letters from the words and result. For each letter, try every digit from 0 to 9 that is not already used, while ensuring that if the letter is the first character of any word, it is not assigned 0. Once all letters are assigned, convert each word to its numerical value and verify if their sum equals the numeric value of the result. If a proper mapping is found, return true; otherwise, backtrack and try another assignment.

Code Solutions

def is_solvable(words, result):
    # Gather all unique letters from words and result
    unique_letters = set("".join(words) + result)
    unique_letters = list(unique_letters)
    
    if len(unique_letters) > 10:
        return False

    # Identify letters that cannot map to 0 because they are leading letters in any word or result
    non_zero_letters = set(word[0] for word in words + [result])
    
    # Helper function to convert a word to a number using current assignment
    def word_to_num(word, mapping):
        num = 0
        for letter in word:
            num = num * 10 + mapping[letter]
        return num

    # Recursive function for backtracking digit assignment
    def backtrack(index, mapping, used):
        if index == len(unique_letters):
            # All letters assigned, evaluate the equation
            total = sum(word_to_num(word, mapping) for word in words)
            return total == word_to_num(result, mapping)
        current_letter = unique_letters[index]
        # Try each digit from 0 to 9
        for digit in range(10):
            # Skip if digit already used or if letter is leading and digit is 0
            if digit in used or (digit == 0 and current_letter in non_zero_letters):
                continue
            mapping[current_letter] = digit
            used.add(digit)
            if backtrack(index + 1, mapping, used):
                return True
            # Backtrack: remove the digit assignment
            used.remove(digit)
            del mapping[current_letter]
        return False
    
    return backtrack(0, {}, set())

# Example usage:
print(is_solvable(["SEND", "MORE"], "MONEY"))  # Expected output: True
print(is_solvable(["LEET", "CODE"], "POINT"))    # Expected output: False