Verbal Arithmetic Puzzle - Leetcode Solution

At the time of writing this answer, there are 4 Verbal Arithmetic Puzzle problems on LeetCode:

1. Word Ladder II (https://leetcode.com/problems/word-ladder-ii/)
2. Verbal Arithmetic Puzzle (https://leetcode.com/problems/verbal-arithmetic-puzzle/)
3. Find Words That Can Be Formed by Characters (https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/)
4. Word Search II (https://leetcode.com/problems/word-search-ii/)

In this answer, we will focus on the Verbal Arithmetic Puzzle problem.

Problem Statement

Given an equation like "SEND + MORE = MONEY", where each letter represents a unique digit from 0 to 9, and the equation is guaranteed to have a valid solution, find the digits that each letter represents.

Example:

Input: "SEND + MORE = MONEY" Output: { "S": 9, "E": 5, "N": 6, "D": 7, "M": 1, "O": 0, "R": 8, "Y": 2 }

Solution Approach

The problem can be solved using a recursive backtracking algorithm. We start by creating a mapping of each letter to a digit, and then try to solve the equation.

For example, if we have the equation "SEND + MORE = MONEY", we can create a mapping like {S: _, E: _, N: _, D: _, M: _, O: _, R: _, Y: _}.

Next, we try to fill in the numbers for each letter, one by one. We start with the first letter, and try all possible digits from 0 to 9. For each digit, we check if the equation is valid so far. If it is, we recursively try to fill in the next letter. If we reach the end of the equation and all digits have been filled, we have found a solution.

If at any point, we find that the equation is not valid, we backtrack to the previous letter and try a different digit. This is the recursive backtracking algorithm.

One important thing to note is that we have to keep track of the carries while adding two numbers. For example, consider the case where S=1 and E=2 in the equation "SEND + MORE = MONEY". When we add S+E, we get a carry of 1. So, when we add N+R+1, we have to account for this carry. Similarly, when we add E+O, we have to check if there is a carry from the previous addition.

Code Implementation

The following is a Python implementation of the recursive backtracking algorithm:

class Solution:
    def is_valid(self, mapping, s1, s2, s3):
        n1 = self.get_number(mapping, s1)
        n2 = self.get_number(mapping, s2)
        n3 = self.get_number(mapping, s3)
        return n1 + n2 == n3
    
    def get_number(self, mapping, s):
        res = 0
        for c in s:
            res = res * 10 + mapping[c]
        return res
    
    def solve(self, idx, carry, mapping, s1, s2, s3):
        if idx == len(s3):
            return carry == 0
        c1 = s1[-1 - idx] if idx < len(s1) else ''
        c2 = s2[-1 - idx] if idx < len(s2) else ''
        c3 = s3[-1 - idx]
        if c3 in mapping:
            if mapping[c3] != carry:
                return False
            return self.solve(idx+1, 0, mapping, s1, s2, s3)
        for d in range(10):
            if str(d) in mapping.values():
                continue
            if d == 0 and (c1 == '' or c2 == '' or c3 == ''):
                continue
            n1 = mapping.get(c1, 0)
            n2 = mapping.get(c2, 0)
            s = n1 + n2 + carry
            if s % 10 != d:
                continue
            mapping[c3] = d
            if self.solve(idx+1, s//10, mapping, s1, s2, s3):
                return True
            del mapping[c3]
        return False
        
    def solvePuzzle(self, words: List[str], result: str) -> Dict[str, int]:
        mapping = {}
        s1, s2, s3 = words[0], words[1], result
        if len(s3) > len(s1) + len(s2):
            return {}
        s1, s2 = s1.zfill(len(s3)), s2.zfill(len(s3))
        if self.solve(0, 0, mapping, s1, s2, s3):
            return mapping
        return {}

The is_valid() function checks if the equation is valid so far. The get_number() function converts a string to the corresponding integer based on the current mapping.

The solve() function is the recursive backtracking algorithm. It takes as input the current index (i.e., the position of the letter/digit that we are trying to fill), the current carry, the current mapping, and the three strings s1, s2, s3. If we have filled all letters, and the equation is valid, we return True. Otherwise, we try to fill the current letter using all possible digits. If we find a valid mapping, we recursively try to fill the next letter. If we reach the end of the equation and all digits have been filled, we have found a solution.

The solvePuzzle() function takes as input the two lists of strings representing the two words and the result, and returns a dictionary mapping each letter to the corresponding digit. It first creates the initial mapping, and then calls the solve() function to find the solution.

Complexity Analysis

The worst-case time complexity of the algorithm is O(10^n), where n is the number of unique letters in the equation. This is because we have to try all possible digits for each letter. However, in practice, the algorithm is much faster because we can prune the search tree by checking if the equation is valid at each point.

The worst-case space complexity of the algorithm is also O(n), where n is the number of unique letters in the equation. This is because we have to store the mapping for each letter. However, in practice, the space complexity is much lower because we can reuse the same mapping for each recursive call.

Conclusion

The Verbal Arithmetic Puzzle problem can be solved using a recursive backtracking algorithm that tries all possible combinations of digits for each letter. The key idea is to use the is_valid() function to check if the equation is valid at each point, and backtrack whenever we encounter an invalid state. The algorithm has a worst-case time complexity of O(10^n) and a worst-case space complexity of O(n), where n is the number of unique letters in the equation.

1