Verbal Arithmetic Puzzle LeetCode

Verbal Arithmetic Puzzle LeetCode problem involves solving a cryptarithm, a type of mathematical puzzle where the digits are replaced by letters. The main goal is to find a substitution of digits for the letters that makes the arithmetic equation valid. Solving this problem will enhance the ability to work with permutations, handle backtracking, and manage edge cases, such as leading zeros in the results. These skills are essential for more complex algorithms and data structures.

Problem statement

Given an equation, represented as a list of strings words and a string result, the task is to assign each letter a unique digit from $0$ to $9$ such that the equation is satisfied. Each string in words and the result string represents a non-negative integer without leading zeros.

Return TRUE if a valid assignment exists, otherwise return FALSE.

Note: There are at most 10 unique letters in the equation.

Constraints:

$2\leq$ words.length $\leq 5$
$1 \leq$ words[i].length, result.length $\leq 7$
words[i], result contain only uppercase English letters.

Let’s take a look at a few examples to get a better understanding of the problem statement:

Solution

To solve the Verbal Arithmetic Puzzle LeetCode problem, we will use backtracking to try all possible digit assignments to letters. We start by mapping each unique letter to a digit and ensure no leading zeros for the numbers formed. If we find a valid assignment that satisfies the equation, we return TRUE. Otherwise, we return FALSE.

Let’s look at the algorithm:

First, we combine all the words and the result into a single string.
Then, we identify all unique letters from this combined string. These letters will be the ones to which we need to assign unique digits from $0$ to $9$ .
We generate all possible permutations of digits (0 to 9) of length equal to the number of unique letters.
Then, we create a mapping of letters to digits based on these permutations.
For each permutation (i.e., each possible assignment of digits to letters) we do the following:
- Map each letter to its corresponding digit.
- Ensure no word in words or result starts with a zero unless the word is exactly "0".
Convert each word in the words array and the result string into their corresponding numerical values using the current letter-to-digit mapping.
Finally, we calculate the sum of the numerical values of the words and verify the equation.

Let’s look at the code for the algorithm we just discussed.

from itertools import permutations
def is_solvable(words, result):
    # Extract all unique characters
    unique_chars = set(''.join(words) + result)
    
    # More than 10 unique characters means no valid solution
    if len(unique_chars) > 10:
        return False 
    # Try all permutations of digits for the unique characters
    for perm in permutations(range(10), len(unique_chars)):
        char_to_digit = dict(zip(unique_chars, perm))
        
        # Check for leading zeros
        if any(char_to_digit[word[0]] == 0 for word in words + [result]):
            continue
        
        # Calculate the sum of words and check against the result
        if sum(to_int(word, char_to_digit) for word in words) == to_int(result, char_to_digit):
            return True
    return False
# Helper function to convert letters to digits
def to_int(word, char_to_digit):
    return int(''.join(str(char_to_digit[char]) for char in word))
    
# Driver code
def main():
    test_cases = [
        (["SEND", "MORE"], "MONEY"),  
        (["LEET", "CODE"], "POINT"),
        (["THIS", "IS"], "TRUE")
    ]
    for i, (words, result) in enumerate(test_cases):
        print(f'{i + 1}. \tGiven words: {words}, result: {result}')
        solvable = is_solvable(words, result)  # Renamed variable to avoid conflict
        print(f'\tThe result: {solvable}')
        print('-' * 100)
if __name__ == '__main__':
    main()

Verbal Arithmetic Puzzle

Verbal Arithmetic Puzzle LeetCode

Problem statement

Knowledge test

Solution

Time complexity

Space complexity