#1307

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Verbal Arithmetic Puzzle

Check if a verbal arithmetic equation can be solved using a valid digit-letter mapping.

Problem Statement

You are given a verbal arithmetic equation, where words on the left side need to be added, and the result is on the right side. Each letter represents a distinct digit, and the task is to verify whether there is a valid mapping such that the sum of the words equals the result. The equation's validity relies on the rule that no two letters can correspond to the same digit.

For example, given the words ["SEND", "MORE"] and the result "MONEY", you must check if there is a way to assign digits to letters such that the equation SEND + MORE = MONEY holds true. The characters involved must map to unique digits, with the constraint that the number of unique characters used in the equation is at most 10.

Examples

Example 1

Input: words = ["SEND","MORE"], result = "MONEY"

Output: true

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

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

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 Approach

Backtracking Search

The problem can be solved using backtracking search, where we explore all possible digit assignments for the characters. At each step, we assign a digit to an unassigned character, and recursively check if the equation holds. If a conflict occurs or the sum doesn't match the result, we prune the search and backtrack to try another digit assignment.

Pruning to Optimize Search

Pruning is essential to optimize the search process. By checking for invalid assignments early, such as repeated digits or leading zeros in multi-digit numbers, we avoid unnecessary calculations. This reduces the search space and improves the efficiency of the algorithm.

Validating the Solution

Once a digit-to-letter mapping is found, we need to validate the solution by checking if the sum of the words matches the result. If it does, the equation is solvable, otherwise, we discard the current mapping and continue the search.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem is exponential, as we must explore all possible mappings of characters to digits. With a maximum of 10 characters and 10 digits, there are 10! possible mappings, but pruning techniques significantly reduce the search space. The space complexity is O(1), as we only need to store the current state of the mappings and a few variables during the search process.

What Interviewers Usually Probe

Look for an understanding of backtracking and its application in solving constraint satisfaction problems.
Candidates should demonstrate awareness of pruning techniques to optimize the search.
The ability to handle edge cases such as leading zeros and duplicate digit mappings is crucial.

Common Pitfalls or Variants

Common pitfalls

Not pruning effectively, leading to an inefficient search that takes too long to complete.
Assigning the same digit to multiple characters, violating the problem's constraints.
Failing to handle leading zeros in the result or words, which can invalidate the solution.

Follow-up variants

Allowing the equation to involve subtraction or multiplication instead of addition.
Reducing the number of words and increasing the result's length to test algorithm efficiency.
Introducing additional constraints, such as limiting the number of digits or allowing for negative digits.

FAQ

What is the core approach for solving the Verbal Arithmetic Puzzle?

The problem is solved using backtracking with pruning, where each letter is mapped to a unique digit, and the solution is validated by checking if the equation holds true.

What should be considered when performing pruning in this problem?

Pruning should handle cases like repeated digits, leading zeros, and invalid mappings early in the process to avoid unnecessary exploration of incorrect solutions.

How does backtracking improve efficiency in this problem?

Backtracking allows for exploring different digit-letter assignments while pruning invalid branches of the search tree, which significantly reduces the search space and enhances performance.

Can this problem be solved using dynamic programming?

No, dynamic programming is not applicable to this problem because it is a constraint satisfaction problem that requires exploring all potential combinations of mappings.

What is the time complexity of solving the Verbal Arithmetic Puzzle?

The time complexity is exponential, around O(10!), due to the need to explore all possible digit mappings. However, pruning significantly reduces the number of explored branches.

terminal

Solution

Solution 1

#### Python3

100

class Solution:
    def isAnyMapping(
        self, words, row, col, bal, letToDig, digToLet, totalRows, totalCols
    ):
        # If traversed all columns.
        if col == totalCols:
            return bal == 0

        # At the end of a particular column.
        if row == totalRows:
            return bal % 10 == 0 and self.isAnyMapping(
                words, 0, col + 1, bal // 10, letToDig, digToLet, totalRows, totalCols
            )

        w = words[row]

        # If the current string 'w' has no character in the ('col')th index.
        if col >= len(w):
            return self.isAnyMapping(
                words, row + 1, col, bal, letToDig, digToLet, totalRows, totalCols
            )

        # Take the current character in the variable letter.
        letter = w[len(w) - 1 - col]

        # Create a variable 'sign' to check whether we have to add it or subtract it.
        if row < totalRows - 1:
            sign = 1
        else:
            sign = -1

        # If we have a prior valid mapping, then use that mapping.
        # The second condition is for the leading zeros.
        if letter in letToDig and (
            letToDig[letter] != 0
            or (letToDig[letter] == 0 and len(w) == 1)
            or col != len(w) - 1
        ):

            return self.isAnyMapping(
                words,
                row + 1,
                col,
                bal + sign * letToDig[letter],
                letToDig,
                digToLet,
                totalRows,
                totalCols,
            )

        # Choose a new mapping.
        else:
            for i in range(10):
                # If 'i'th mapping is valid then select it.
                if digToLet[i] == "-" and (
                    i != 0 or (i == 0 and len(w) == 1) or col != len(w) - 1
                ):
                    digToLet[i] = letter
                    letToDig[letter] = i

                    # Call the function again with the new mapping.
                    if self.isAnyMapping(
                        words,
                        row + 1,
                        col,
                        bal + sign * letToDig[letter],
                        letToDig,
                        digToLet,
                        totalRows,
                        totalCols,
                    ):
                        return True

                    # Unselect the mapping.
                    digToLet[i] = "-"
                    if letter in letToDig:
                        del letToDig[letter]

        # If nothing is correct then just return false.
        return False

    def isSolvable(self, words, result):
        # Add the string 'result' in the list 'words'.
        words.append(result)

        # Initialize 'totalRows' with the size of the list.
        totalRows = len(words)

        # Find the longest string in the list and set 'totalCols' with the size of that string.
        totalCols = max(len(word) for word in words)

        # Create a HashMap for the letter to digit mapping.
        letToDig = {}

        # Create a list for the digit to letter mapping.
        digToLet = ["-"] * 10

        return self.isAnyMapping(
            words, 0, 0, 0, letToDig, digToLet, totalRows, totalCols
        )

Continue Practicing

#1255 maximum score words formed by letters #1239 maximum length of a concatenated string with unique characters #1467 probability of a two boxes having the same number of distinct balls