Formatted question description: https://leetcode.ca/all/1307.html

1307. Verbal Arithmetic Puzzle (Hard)

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

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

Each character is decoded as one digit (0 - 9).
Every pair of different characters they must map to different digits.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on left side (words) will equal to the number on 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 = ["THIS","IS","TOO"], result = "FUNNY"
Output: true

Example 4:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false

Constraints:

2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contains only upper case English letters.
Number of different characters used on the expression is at most 10.

Related Topics:
Math, Backtracking

Solution 1. Backtracking

Try to map the characters from right to left so that we can check the validity along the way.

Time complexity

Assume the maximum length of result or words[i] is L, and words is of length W.

There are L! permutations. For each permutation, we need to check validity. Checking validity takes O(LW). We check validity when each new character is mapped, so we check L times for a permutation.

So overall the time complexity is O(L! * L^2 * W).

// OJ: https://leetcode.com/problems/verbal-arithmetic-puzzle/
// Time: O(L! * L^2 * W)
// Space: O(L)
class Solution {
    unordered_map<char, int> m; // map from char to the corresponding integer
    vector<char> chs; // chars to consider, right most chars are first considered.
    unordered_set<char> leading; // leading chars can't be zero
    int used[10] = {}; // digit `i` is used if `used[i] == 1`
    bool valid(vector<string>& words, string result) { // check if the current map `m` is valid
        int sum = 0;
        for (int i = 0; i < result.size(); ++i) {
            for (auto &w : words) {
                if (i >= w.size()) continue;
                char c = w[w.size() - i - 1];
                if (m.count(c) == 0) return true;
                sum += m[c];
            }
            char c = result[result.size() - i - 1];
            if (m.count(c) == 0) return true;
            sum -= m[c];
            if (sum % 10) return false;
            sum /= 10;
        }
        return true;
    }
    bool dfs(vector<string>& words, string result, int index) {
        if (index == chs.size()) return true;
        for (int i = 0; i < 10; ++i) {
            if (used[i] || (i == 0 && leading.count(chs[index]))) continue;
            used[i] = 1;
            m[chs[index]] = i;
            if (valid(words, result) && dfs(words, result, index + 1)) return true;
            m.erase(chs[index]);
            used[i] = 0;
        }
        return false;
    }
    void addChar(char ch) {
        for (char c : chs) {
            if (c == ch) return;
        }
        chs.push_back(ch);
    }
public:
    bool isSolvable(vector<string>& words, string result) {
        for (auto &w : words) {
            if (w.size() > result.size()) return false;
            if (w.size() > 1) leading.insert(w[0]);
        }
        if (result.size() > 1) leading.insert(result[0]);
        for (int i = 0; i < result.size(); ++i) {
            for (auto &w : words) {
                if (i < w.size()) addChar(w[w.size() - i - 1]);
            }
            addChar(result[result.size() - i - 1]);
        }
        return dfs(words, result, 0);
    }
};

Java
Python

class Solution {
    public boolean isSolvable(String[] words, String result) {
        Map<Character, Integer> letterDigitMap = new HashMap<Character, Integer>();
        Set<Character> leadingSet = new HashSet<Character>();
        int resultLength = result.length();
        for (String word : words) {
            if (word.length() > resultLength)
                return false;
            if (word.length() > 1)
                leadingSet.add(word.charAt(0));
        }
        if (result.length() > 1)
            leadingSet.add(result.charAt(0));
        boolean[] used = new boolean[10];
        int[] carry = new int[resultLength + 1];
        return depthFirstSearch(words, result, letterDigitMap, leadingSet, used, carry, 0, 0);
    }

    public boolean depthFirstSearch(String[] words, String result, Map<Character, Integer> letterDigitMap, Set<Character> leadingSet, boolean[] used, int[] carry, int position, int wordIndex) {
        if (position == result.length())
            return carry[position] == 0;
        else if (wordIndex < words.length) {
            String word = words[wordIndex];
            int wordLength = word.length();
            if (wordLength <= position || letterDigitMap.containsKey(word.charAt(wordLength - position - 1)))
                return depthFirstSearch(words, result, letterDigitMap, leadingSet, used, carry, position, wordIndex + 1);
            else {
                char letter = word.charAt(wordLength - position - 1);
                int start = leadingSet.contains(letter) ? 1 : 0;
                for (int i = start; i <= 9; i++) {
                    if (!used[i]) {
                        used[i] = true;
                        letterDigitMap.put(letter, i);
                        boolean next = depthFirstSearch(words, result, letterDigitMap, leadingSet, used, carry, position, wordIndex + 1);
                        used[i] = false;
                        letterDigitMap.remove(letter);
                        if (next)
                            return true;
                    }
                }
            }
            return false;
        } else {
            int remain = carry[position];
            for (String word : words) {
                if (word.length() > position) {
                    char letter = word.charAt(word.length() - position - 1);
                    remain += letterDigitMap.get(letter);
                }
            }
            carry[position + 1] = remain / 10;
            remain %= 10;
            char letter = result.charAt(result.length() - position - 1);
            if (letterDigitMap.containsKey(letter) && letterDigitMap.get(letter) == remain)
                return depthFirstSearch(words, result, letterDigitMap, leadingSet, used, carry, position + 1, 0);
            else if (!letterDigitMap.containsKey(letter) && !used[remain] && !(leadingSet.contains(letter) && remain == 0)) {
                used[remain] = true;
                letterDigitMap.put(letter, remain);
                boolean next = depthFirstSearch(words, result, letterDigitMap, leadingSet, used, carry, position + 1, 0);
                used[remain] = false;
                letterDigitMap.remove(letter);
                return next;
            } else
                return false;
        }
    }
}

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
        )

1307 - Verbal Arithmetic Puzzle

1307. Verbal Arithmetic Puzzle (Hard)

Solution 1. Backtracking

Time complexity

All Problems

All Solutions

Welcome to Subscribe On Youtube

1307. Verbal Arithmetic Puzzle (Hard)

Solution 1. Backtracking

Time complexity

All Problems

All Solutions