1307. 单词数学谜题

Hard

题目描述

给定一个等式，左边是单词数组，右边是结果单词。

你需要检查等式在以下规则下是否可解：

每个字符被解码为一个数字（0-9）
没有两个字符可以映射到相同的数字
每个 words[i] 和 result 被解码为一个没有前导零的数字
左边数字的和等于右边的数字

如果等式可解返回 true，否则返回 false。

示例 1：

输入：words = ["SEND","MORE"], result = "MONEY"
输出：true
解释：映射 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
使得："SEND" + "MORE" = "MONEY"，9567 + 1085 = 10652

示例 2：

输入：words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
输出：true
解释：映射 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
使得："SIX" + "SEVEN" + "SEVEN" = "TWENTY"，650 + 68782 + 68782 = 138214

示例 3：

输入：words = ["LEET","CODE"], result = "POINT"
输出：false
解释：没有可能的映射来满足等式，所以返回 false。
注意两个不同的字符不能映射到相同的数字。

约束条件：

2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result 只包含大写英文字母
表达式中使用的不同字符最多 10 个

解题思路

这是一个经典的回溯算法题目，需要为每个字符分配一个数字使得等式成立。

核心思路：

字符收集与约束识别：首先收集所有出现的字符，并识别哪些字符不能为0（即单词的首字母，会导致前导零）。
从右到左的列计算：采用竖式计算的思想，从最低位开始逐列处理。这样可以利用进位信息进行剪枝优化。
回溯搜索：对于每个未赋值的字符，尝试所有可能的数字（0-9），并检查约束条件。
剪枝优化：
- 检查首字母不为0的约束
- 在每一列计算时，如果当前列的和已经确定但与期望值不符，直接剪枝
- 利用进位信息进行提前判断
列验证：对于每一列，计算所有words在该位的数字和加上上一列的进位，应该等于result在该位的数字加上当前列产生的进位乘以10。

这种从右到左逐列处理的方法比直接计算整个数字更高效，因为可以更早地发现冲突并进行剪枝。

代码实现

class Solution {
public:
    bool isSolvable(vector<string>& words, string result) {
        unordered_set<char> chars;
        unordered_set<char> leading;
        
        // 收集所有字符和首字母
        for (const string& word : words) {
            for (char c : word) chars.insert(c);
            if (word.length() > 1) leading.insert(word[0]);
        }
        for (char c : result) chars.insert(c);
        if (result.length() > 1) leading.insert(result[0]);
        
        vector<char> charList(chars.begin(), chars.end());
        unordered_map<char, int> charToDigit;
        vector<bool> used(10, false);
        
        return backtrack(words, result, charList, 0, charToDigit, used, leading, 0, 0);
    }
    
private:
    bool backtrack(const vector<string>& words, const string& result, 
                  const vector<char>& charList, int index, 
                  unordered_map<char, int>& charToDigit, vector<bool>& used,
                  const unordered_set<char>& leading, int col, int carry) {
        
        if (col == result.length()) {
            return carry == 0;
        }
        
        if (index == charList.size()) {
            return checkColumn(words, result, charToDigit, col, carry);
        }
        
        char c = charList[index];
        for (int digit = 0; digit <= 9; digit++) {
            if (used[digit] || (digit == 0 && leading.count(c))) continue;
            
            charToDigit[c] = digit;
            used[digit] = true;
            
            if (backtrack(words, result, charList, index + 1, charToDigit, used, leading, col, carry)) {
                return true;
            }
            
            charToDigit.erase(c);
            used[digit] = false;
        }
        return false;
    }
    
    bool checkColumn(const vector<string>& words, const string& result,
                    const unordered_map<char, int>& charToDigit, int col, int carry) {
        
        if (col >= result.length()) return carry == 0;
        
        int sum = carry;
        for (const string& word : words) {
            int pos = word.length() - 1 - col;
            if (pos >= 0) {
                sum += charToDigit.at(word[pos]);
            }
        }
        
        int resultPos = result.length() - 1 - col;
        int expectedDigit = charToDigit.at(result[resultPos]);
        
        if (sum % 10 != expectedDigit) return false;
        
        return checkColumn(words, result, charToDigit, col + 1, sum / 10);
    }
};

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        chars = set()
        leading = set()
        
        # 收集所有字符和首字母
        for word in words:
            chars.update(word)
            if len(word) > 1:
                leading.add(word[0])
        
        chars.update(result)
        if len(result) > 1:
            leading.add(result[0])
        
        char_list = list(chars)
        char_to_digit = {}
        used = [False] * 10
        
        def check_column(col, carry):
            if col >= len(result):
                return carry == 0
            
            total = carry
            for word in words:
                pos = len(word) - 1 - col
                if pos >= 0:
                    total += char_to_digit[word[pos]]
            
            result_pos = len(result) - 1 - col
            expected = char_to_digit[result[result_pos]]
            
            if total % 10 != expected:
                return False
            
            return check_column(col + 1, total // 10)
        
        def backtrack(index, col, carry):
            if col == len(result):
                return carry == 0
            
            if index == len(char_list):
                return check_column(col, carry)
            
            char = char_list[index]
            for digit in range(10):
                if used[digit] or (digit == 0 and char in leading):
                    continue
                
                char_to_digit[char] = digit
                used[digit] = True
                
                if backtrack(index + 1, col, carry):
                    return True
                
                del char_to_digit[char]
                used[digit] = False
            
            return False
        
        return backtrack(0, 0, 0)

public class Solution {
    public bool IsSolvable(string[] words, string result) {
        HashSet<char> chars = new HashSet<char>();
        HashSet<char> leading = new HashSet<char>();
        
        // 收集所有字符和首字母
        foreach (string word in words) {
            foreach (char c in word) chars.Add(c);
            if (word.Length > 1) leading.Add(word[0]);
        }
        foreach (char c in result) chars.Add(c);
        if (result.Length > 1) leading.Add(result[0]);
        
        char[] charList = new char[chars.Count];
        chars.CopyTo(charList);
        Dictionary<char, int> charToDigit = new Dictionary<char, int>();
        bool[] used = new bool[10];
        
        return Backtrack(words, result, charList, 0, charToDigit, used, leading, 0, 0);
    }
    
    private bool Backtrack(string[] words, string result, char[] charList, int index,
                          Dictionary<char, int> charToDigit, bool[] used,
                          HashSet<char> leading, int col, int carry) {
        
        if (col == result.Length) {
            return carry == 0;
        }
        
        if (index == charList.Length) {
            return CheckColumn(words, result, charToDigit, col, carry);
        }
        
        char c = charList[index];
        for (int digit = 0; digit <= 9; digit++) {
            if (used[digit] || (digit == 0 && leading.Contains(c))) continue;
            
            charToDigit[c] = digit;
            used[digit] = true;
            
            if (Backtrack(words, result, charList, index + 1, charToDigit, used, leading, col, carry)) {
                return true;
            }
            
            charToDigit.Remove(c);
            used[digit] = false;
        }
        return false;
    }
    
    private bool CheckColumn(string[] words, string result, Dictionary<char, int> charToDigit, int col, int carry) {
        if (col >= result.Length) return carry == 0;
        
        int sum = carry;
        foreach (string word in words) {
            int pos = word.Length - 1 - col;
            if (pos >= 0) {
                sum += charToDigit[word[pos]];
            }
        }
        
        int resultPos = result.Length - 1 - col;
        int expectedDigit = charToDigit[result[resultPos]];
        
        if (sum % 10 != expectedDigit) return false;
        
        return CheckColumn(words, result, charToDigit, col + 1, sum / 10);
    }
}

var isSolvable = function(words, result) {
    const chars = new Set();
    for (let word of words) {
        for (let char of word) {
            chars.add(char);
        }
    }
    for (let char of result) {
        chars.add(char);
    }
    
    const charList = Array.from(chars);
    const assignment = {};
    const used = new Array(10).fill(false);
    
    const firstChars = new Set();
    for (let word of words) {
        if (word.length > 1) {
            firstChars.add(word[0]);
        }
    }
    if (result.length > 1) {
        firstChars.add(result[0]);
    }
    
    function backtrack(index) {
        if (index === charList.length) {
            return isValid();
        }
        
        const char = charList[index];
        for (let digit = 0; digit <= 9; digit++) {
            if (used[digit]) continue;
            if (digit === 0 && firstChars.has(char)) continue;
            
            assignment[char] = digit;
            used[digit] = true;
            
            if (backtrack(index + 1)) {
                return true;
            }
            
            used[digit] = false;
            delete assignment[char];
        }
        
        return false;
    }
    
    function isValid() {
        let sum = 0;
        for (let word of words) {
            let num = 0;
            for (let char of word) {
                num = num * 10 + assignment[char];
            }
            sum += num;
        }
        
        let resultNum = 0;
        for (let char of result) {
            resultNum = resultNum * 10 + assignment[char];
        }
        
        return sum === resultNum;
    }
    
    return backtrack(0);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(10!)	在最坏情况下需要尝试所有字符的数字分配，最多10个字符对应10!种排列
空间复杂度	O(k)	k为字符数量，用于存储字符映射和使用状态，递归深度也为O(k)

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析