The Verbal Arithmetic Puzzle (also known as Alphametics or Cryptarithmetic) asks you to determine if a set of words can be assigned digits (0-9) such that when the words are interpreted as numbers and summed, they equal a given result word. Each letter represents a unique digit, and no word can start with the digit zero.
You are given a list of strings words and a string result. Each string contains only uppercase English letters. Assign a digit to each unique letter so that:
result) starts with the digit 0.words equals the integer value of result.
Return true if there is at least one valid assignment; otherwise, return false.
Key Constraints:
At first glance, it seems like we could try every possible mapping of digits to letters, but with up to 10 unique letters, there are 10! (3,628,800) possible assignments. This brute-force approach is computationally expensive.
To optimize, we notice:
Let's break down the algorithm step-by-step:
words and result.false (since only digits 0-9 are available).We use a hash map for fast letter-to-digit lookup, and a set to track used digits. This approach is efficient because it prunes large portions of the search space that can't possibly lead to a solution.
Let's consider the classic example:
words = ["SEND", "MORE"]
result = "MONEY"
The algorithm tries assignments recursively, skipping any that violate the constraints (e.g., reusing a digit, leading zeros), and backtracks when necessary.
Brute-force Approach:
The solution is feasible due to the small number of unique letters (max 10) and the aggressive pruning from backtracking.
The Verbal Arithmetic Puzzle is a classic constraint satisfaction problem. By representing the puzzle as a set of equations and using backtracking with pruning, we efficiently search for a valid mapping of letters to digits. The key insights are:
class Solution:
def isSolvable(self, words, result):
from collections import defaultdict
# Step 1: Find all unique letters
letters = set()
first_letters = set()
for word in words + [result]:
letters |= set(word)
first_letters.add(word[0])
letters = list(letters)
if len(letters) > 10:
return False
# Step 2: Calculate weights for each letter
weights = defaultdict(int)
for word in words:
for i, c in enumerate(word[::-1]):
weights[c] += 10 ** i
for i, c in enumerate(result[::-1]):
weights[c] -= 10 ** i
# Step 3: Backtracking
def backtrack(idx, assignment, used_digits):
if idx == len(letters):
# Check if the weighted sum is zero
return sum(weights[c] * assignment[c] for c in letters) == 0
c = letters[idx]
for d in range(10):
if d in used_digits:
continue
if d == 0 and c in first_letters:
continue
assignment[c] = d
used_digits.add(d)
if backtrack(idx + 1, assignment, used_digits):
return True
used_digits.remove(d)
del assignment[c]
return False
return backtrack(0, dict(), set())
class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
vector<char> letters;
unordered_set<char> unique_letters, first_letters;
for (auto& word : words) {
for (char c : word) unique_letters.insert(c);
first_letters.insert(word[0]);
}
for (char c : result) {
unique_letters.insert(c);
first_letters.insert(result[0]);
}
for (char c : unique_letters) letters.push_back(c);
if (letters.size() > 10) return false;
unordered_map<char, int> weights;
for (auto& word : words) {
int n = word.size();
for (int i = 0; i < n; ++i)
weights[word[n - i - 1]] += pow(10, i);
}
int n = result.size();
for (int i = 0; i < n; ++i)
weights[result[n - i - 1]] -= pow(10, i);
function<bool(int, unordered_map<char, int>&, unordered_set<int>&)> backtrack;
backtrack = [&](int idx, unordered_map<char, int>& assign, unordered_set<int>& used) {
if (idx == letters.size()) {
long sum = 0;
for (auto& c : letters)
sum += weights[c] * assign[c];
return sum == 0;
}
char c = letters[idx];
for (int d = 0; d < 10; ++d) {
if (used.count(d)) continue;
if (d == 0 && first_letters.count(c)) continue;
assign[c] = d;
used.insert(d);
if (backtrack(idx + 1, assign, used)) return true;
used.erase(d);
assign.erase(c);
}
return false;
};
unordered_map<char, int> assign;
unordered_set<int> used;
return backtrack(0, assign, used);
}
};
import java.util.*;
class Solution {
public boolean isSolvable(String[] words, String result) {
Set<Character> uniqueLetters = new HashSet<>();
Set<Character> firstLetters = new HashSet<>();
for (String word : words) {
for (char c : word.toCharArray()) uniqueLetters.add(c);
firstLetters.add(word.charAt(0));
}
for (char c : result.toCharArray()) uniqueLetters.add(c);
firstLetters.add(result.charAt(0));
if (uniqueLetters.size() > 10) return false;
List<Character> letters = new ArrayList<>(uniqueLetters);
Map<Character, Integer> weights = new HashMap<>();
for (String word : words) {
int n = word.length();
for (int i = 0; i < n; ++i) {
char c = word.charAt(n - i - 1);
weights.put(c, weights.getOrDefault(c, 0) + (int)Math.pow(10, i));
}
}
int n = result.length();
for (int i = 0; i < n; ++i) {
char c = result.charAt(n - i - 1);
weights.put(c, weights.getOrDefault(c, 0) - (int)Math.pow(10, i));
}
return backtrack(0, letters, weights, new HashMap<>(), new HashSet<>(), firstLetters);
}
private boolean backtrack(int idx, List<Character> letters, Map<Character, Integer> weights,
Map<Character, Integer> assign, Set<Integer> used, Set<Character> firstLetters) {
if (idx == letters.size()) {
int sum = 0;
for (char c : letters)
sum += weights.get(c) * assign.get(c);
return sum == 0;
}
char c = letters.get(idx);
for (int d = 0; d < 10; ++d) {
if (used.contains(d)) continue;
if (d == 0 && firstLetters.contains(c)) continue;
assign.put(c, d);
used.add(d);
if (backtrack(idx + 1, letters, weights, assign, used, firstLetters)) return true;
assign.remove(c);
used.remove(d);
}
return false;
}
}
var isSolvable = function(words, result) {
const unique = new Set(), firstLetters = new Set();
for (const word of words) {
for (const c of word) unique.add(c);
firstLetters.add(word[0]);
}
for (const c of result) unique.add(c);
firstLetters.add(result[0]);
const letters = Array.from(unique);
if (letters.length > 10) return false;
const weights = {};
for (const word of words) {
for (let i = 0; i < word.length; ++i) {
const c = word[word.length - i - 1];
weights[c] = (weights[c] || 0) + Math.pow(10, i);
}
}
for (let i = 0; i < result.length; ++i) {
const c = result[result.length - i - 1];
weights[c] = (weights[c] || 0) - Math.pow(10, i);
}
function backtrack(idx, assign, used) {
if (idx === letters.length) {
let sum = 0;
for (const c of letters)
sum += weights[c] * assign[c];
return sum === 0;
}
const c = letters[idx];
for (let d = 0; d < 10; ++d) {
if (used.has(d)) continue;
if (d === 0 && firstLetters.has(c)) continue;
assign[c] = d;
used.add(d);
if (backtrack(idx + 1, assign, used)) return true;
used.delete(d);
delete assign[c];
}
return false;
}
return backtrack(0, {}, new Set());
};