Verbal Arithmetic Puzzle

Hard

Google

1 view

Topics:

ArraysStringsRecursion

Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:

Each character is decoded as one digit (0 - 9).
No two characters can map to the same digit.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on the left side (words) will equal to the number on the right side (result).

Return true if the equation is solvable, otherwise return false.

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.

Constraints:

2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contain only uppercase English letters.
The number of different characters used in the expression is at most 10.

Verbal Arithmetic Puzzle

Hard

Google

1 view

Topics:

ArraysStringsRecursion

Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:

Each character is decoded as one digit (0 - 9).
No two characters can map to the same digit.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on the left side (words) will equal to the number on the right side (result).

Return true if the equation is solvable, otherwise return false.

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.

Constraints:

2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contain only uppercase English letters.
The number of different characters used in the expression is at most 10.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the letters case-sensitive, and should I assume all letters in the input words and the result are uppercase (or lowercase)?
Can the same letter map to '0'? If not, is it guaranteed that the leftmost letter of each word and the result will not map to '0'?
Are the input strings guaranteed to be valid words containing only letters, and will the result string also follow this pattern?
Is there a maximum length for the input words or the result string? This will help me determine if certain integer types may overflow during calculation.
If there are multiple valid solutions, should I return any one of them, or is there a specific solution that is preferred?

Brute Force Solution

Approach

The brute-force strategy for solving verbal arithmetic puzzles involves trying every possible combination of number assignments to the letters. We check if each combination makes the equation true, and if so, we've found a solution. It's like trying every key on a keyring to see which one unlocks a door.

Here's how the algorithm would work step-by-step:

Identify all the unique letters used in the equation.
Assign a different digit (0 through 9) to each unique letter. Start with the very first possibility (for example, A=0, B=1, C=2, and so on).
Substitute these digits for the letters in the equation to get an actual arithmetic equation.
Evaluate the equation. Determine if the equation holds true. For example, does the left side equal the right side?
If the equation is true, then we have found a solution. We are done.
If the equation is false, we need to try a new combination of digits. Systematically change the digits assigned to each letter. Make sure each letter still has a unique digit.
Repeat steps 3 through 6, trying all possible combinations of digit assignments until a solution is found or all possibilities have been exhausted.

Code Implementation

def solve_verbal_arithmetic(equation):
    words = equation.replace('+', ' ').replace('=', ' ').split()
    unique_characters = ''.join(sorted(set(''.join(words))))
    number_of_unique_characters = len(unique_characters)

    if number_of_unique_characters > 10:
        return None

    import itertools
    for digits_permutation in itertools.permutations(range(10), number_of_unique_characters):
        # Assign digits to characters
        character_to_digit = dict(zip(unique_characters, digits_permutation))

        # Check if leading digit is zero
        if any(character_to_digit[word[0]] == 0 for word in words):
            continue

        # Evaluate the equation
        values = [int(''.join(str(character_to_digit[character]) for character in word)) for word in words]
        if len(values) >= 3:
            if values[-1] == sum(values[:-1]):
                return character_to_digit
    return None

Big(O) Analysis

Time Complexity

O(10^k) – The brute-force approach iterates through all possible assignments of digits (0-9) to the unique letters in the equation. Let k be the number of unique letters. Since each of the k letters can be assigned a digit from 0 to 9, there are 10 options for the first letter, 9 for the second (because digits must be unique), 8 for the third, and so on. This results in 10 * 9 * 8 * ... * (10 - k + 1) possible combinations. In the worst-case scenario, we might have to try all these combinations before finding a solution or determining that no solution exists. Therefore, the time complexity is proportional to the number of combinations, which can be expressed as a permutation. Since the number of combinations is driven by the number of unique letters and is capped by the number of digits (10), we can denote the time complexity as O(10^k), where k is the number of unique letters. Note that while technically a permutation, in Big O notation, we focus on the exponential growth driven by the number of possible assignments.

Space Complexity

O(10) – The brute-force algorithm identifies unique letters, up to a maximum of 10, and assigns digits to them. This assignment process inherently requires storing the mapping between letters and digits, which can be represented using a hash map or an array of size up to 10. Therefore, the algorithm uses auxiliary space to store digit assignments for each letter. Since there are at most 10 unique digits, the space used for the letter-to-digit mapping is constant. This constant auxiliary space usage is O(10), which simplifies to O(1).

Optimal Solution

Approach

The most efficient way to solve this puzzle is to use constraint satisfaction and backtracking. We assign digits to letters one by one, checking if the partial solution is still valid based on the arithmetic rules. If it's not valid, we backtrack and try a different digit.

Here's how the algorithm would work step-by-step:

First, figure out which letters represent which digits. Start with the letters that appear in the leftmost columns of the words; these have the biggest impact on the sum.
Try assigning a digit to a letter. Check if assigning that digit leads to a conflict. For example, two different letters cannot have the same digit, and the leading digit of a number cannot be zero.
After assigning a digit, check if the arithmetic equation still works. This might require looking at the partial sums.
If assigning a digit creates a conflict or makes the equation wrong, undo the assignment and try a different digit for the same letter.
If you've tried all digits for a letter and none of them work, go back to the previous letter and try a different digit for *that* letter. This is called backtracking.
Keep repeating this process of assigning digits, checking for conflicts, and backtracking until you find a combination of digits that solves the entire puzzle or you've exhausted all possibilities.
When checking the arithmetic equation, it's much faster to only look at the equation using only the digits that are assigned at the moment. If the partial equation is false, the entire expression will be false. If the partial equation is true, you can move to the next unknown digit

Code Implementation

def solve_verbal_arithmetic(equation):
    words = equation.replace('+', ' ').replace('=', ' ').split()
    unique_characters = ''.join(sorted(set(''.join(words))))
    first_letters = {word[0] for word in words}

    def string_to_number(word, letter_to_digit):
        number = 0
        for char in word:
            number = number * 10 + letter_to_digit[char]
        return number

    def is_solution_valid(letter_to_digit, words):
        left_side = sum(string_to_number(word, letter_to_digit) for word in words[:-1])
        right_side = string_to_number(words[-1], letter_to_digit)
        return left_side == right_side

    def solve(index, letter_to_digit, used_digits):
        if index == len(unique_characters):
            return is_solution_valid(letter_to_digit, words)

        letter = unique_characters[index]

        for digit in range(10):
            if digit in used_digits:
                continue

            # Leading zeros aren't allowed
            if digit == 0 and letter in first_letters:
                continue

            letter_to_digit[letter] = digit
            used_digits.add(digit)

            # Backtrack to explore other possibilities
            if solve(index + 1, letter_to_digit, used_digits):
                return True

            # Reset for backtracking step to find solution
            used_digits.remove(digit)
            del letter_to_digit[letter]

        return False

    letter_to_digit = {}
    used_digits = set()

    if solve(0, letter_to_digit, used_digits):
        return letter_to_digit
    else:
        return None

Big(O) Analysis

Time Complexity

O(10^n) – The algorithm uses backtracking to try all possible digit assignments to the letters. In the worst case, each of the n distinct letters in the puzzle could potentially be assigned each of the 10 digits (0-9). Therefore, the algorithm explores a search space where each letter has 10 possible values. This leads to an exponential number of possibilities, specifically 10 raised to the power of n, where n is the number of distinct letters. While constraint satisfaction and pruning can reduce the search space in practice, the worst-case time complexity remains exponential.

Space Complexity

O(10) – The algorithm uses a hash map (or array) to store the digit assignments for each letter, which is at most 10 since there are at most 10 unique digits (0-9). Additionally, it uses a boolean array (or set) to track which digits have been assigned. Furthermore, the recursion stack's depth is at most the number of unique letters, which is also capped at 10. Thus, the auxiliary space remains constant, regardless of the length of the input words, and is O(10), which simplifies to O(1).

Edge Cases

Case	How to Handle
Empty input strings for words or result	Return false immediately since there is no valid puzzle to solve
Words or result contain characters other than uppercase letters	Reject the input and return false or throw an exception since only uppercase letters are valid
The same letter appears at the beginning of multiple words or the result	Track leading characters to ensure no leading zero constraints are violated during assignment
The length of the result is shorter than one of the input words	Return false immediately since the sum cannot be shorter than the addends
No valid solution exists for the given puzzle	The backtracking search algorithm should exhaust all possibilities and return false if no solution is found
Multiple valid solutions exist	The problem usually asks for only one solution; the algorithm can stop and return the first solution found
Integer overflow during intermediate additions	Use a data type that can accommodate large numbers or check for overflow before assigning values to prevent incorrect calculations
Words or result start with the same letter, and that letter has a value of zero	Ensure that the leading digit cannot be zero during assignment.