LeetCode 1307. 口算难题

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 1307. 口算难题原题链接困难

作者：

wzc1995 , 2020-01-01 13:31:48 , 所有人可见 , 阅读 2718

题目描述

给你一个方程，左边用 words 表示，右边用 result 表示。

你需要根据以下规则检查方程是否可解：

每个字符都会被解码成一位数字（0 - 9）。
每对不同的字符必须映射到不同的数字。
每个 words[i] 和 result 都会被解码成一个没有前导零的数字。
左侧数字之和（words）等于右侧数字（result）。

如果方程可解，返回 True，否则返回 False。

样例

输入：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

输入：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

输入：words = ["THIS","IS","TOO"], result = "FUNNY"
输出：true

输入：words = ["LEET","CODE"], result = "POINT"
输出：false

限制

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

算法

(递归回溯) $O(P_{10}^{c} + nm)$

如果 result 的列数不等于单词列表的最大长度或最大长度加 $1$，则直接返回 false。
为了实现方便，result 放到了 words 的最后，将单词和 result 都做一下翻转，方便处理。我们按照列，从最低位到最高位递归回溯。
递归的状态为 (c, r, carry)，表示当前在第 c 位，第 r 个单词（r 等于单词列表长度时，视为在 result 单词上），上一位的进位记为 carry。
当遍历完当前列的所有单词（包括 result 时），将这一位所有非 result 单词的和加起来判断是否合法。
对于这一列中没有确定的字母，则枚举这个字母对应哪个数字。注意判断前导零。

时间复杂度

设 $n$ 为单词的个数，$m$ 为列数，$c$ 为不同字母的个数。
最坏情况下，需要从 $10$ 个数字里选出 $c$ 个数字，一共有 $O(nm)$ 个字母，故时间复杂度最坏为 $O(P_{10}^{c} + nm)$。

空间复杂度

递归的层数最坏有 $O(nm)$ 层，故空间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    bool solve(int c, int r, int carry, size_t max_len,
              vector<int> &mp,
              vector<int> &used,
              const vector<string> &words) {

        if (c == max_len)
            return carry == 0;

        if (r == words.size()) {
            int sum = carry;

            for (int i = 0; i < words.size() - 1; i++)
                if (c < words[i].size())
                    sum += mp[words[i][c] - 'A'];

            if (sum % 10 != mp[words.back()[c] - 'A'])
                return false;

            return solve(c + 1, 0, sum / 10, max_len, mp, used, words);
        }

        if (words[r].size() > 1 && c == words[r].size() - 1 && mp[words[r][c] - 'A'] == 0)
            return false;

        if (c >= words[r].size() || mp[words[r][c] - 'A'] != -1)
            return solve(c, r + 1, carry, max_len, mp, used, words);

        for (int num = 0; num < 10; num++) {
            if (used[num])
                continue;

            used[num] = true;
            mp[words[r][c] - 'A'] = num;

            if (solve(c, r + 1, carry, max_len, mp, used, words))
                return true;

            mp[words[r][c] - 'A'] = -1;
            used[num] = false;
        }

        return false;
    }

    bool isSolvable(vector<string>& words, string result) {
        vector<int> mp(26, -1);
        size_t max_len = 0;
        for (auto &s: words) {
            reverse(s.begin(), s.end());
            max_len = max(max_len, s.size());
        }

        reverse(result.begin(), result.end());

        if (max_len != result.size() && max_len + 1 != result.size())
            return false;

        max_len = max(max_len, result.size());
        words.push_back(result);

        vector<int> used(10, false);

        return solve(0, 0, 0, max_len, mp, used, words);
    }
};

8 评论

panic 2022-08-24 17:50

[“AA”, “BB”] “AA” 这个例子挂了，需要判断如果单词长度大于1，并且开头是0，则直接返回false，if (words[row].size()>1 && col==words[row].size()-1 && letterMap[words[row][col]-‘A’]==0) return false;

class Solution {
public:
    vector<string> words;
    vector<bool> usedNum;
    vector<int> letterMap;
    int len=0;
    bool dfs(int col,int row,int c){
        if (col==len){
            return c==0;
        }
        if (row==words.size()){
            int sum=c;
            for (int i=0;i<words.size()-1;i++)
                if (words[i].size()>col) sum+=letterMap[words[i][col]-'A'];
            if (sum%10!=letterMap[words.back()[col]-'A']) return false;
            return dfs(col+1,0,sum/10);
        }
        if (words[row].size()>1 && col==words[row].size()-1 && letterMap[words[row][col]-'A']==0) return false;
        if (col>=words[row].size() || letterMap[words[row][col]-'A']!=-1) return dfs(col,row+1,c);
        for (int num=0;num<=9;num++){
            if (usedNum[num] || (num==0 && words[row].size()>1 && col==words[row].size()-1)) continue;
            usedNum[num]=true;
            letterMap[words[row][col]-'A']=num;
            if (dfs(col,row+1,c)) return true;
            letterMap[words[row][col]-'A']=-1;
            usedNum[num]=false;
        }
        return false;
    }
    bool isSolvable(vector<string>& _words, string result) {
        words=_words;
        for (auto &s:words){
            reverse(s.begin(),s.end());
            len=max(len,(int)s.size());
        }
        reverse(result.begin(),result.end());
        if (len!=result.size() && len+1!=result.size()) return false;
        len=max(len,(int)result.size());
        words.push_back(result);
        usedNum=vector<bool>(10);
        letterMap=vector<int>(26,-1);
        return dfs(0,0,0);
    }
};

wzc1995 2022-08-26 14:01

感谢 commnet，已修复

@Dorian 2020-02-17 01:54

大佬，[“AA”, “BB”] “AA”这个test case怎么败了out put true, expected false.
这个为true不是只能B = 0，违背了前导0的要求。
num == 0 && c == words[r].size() - 1)这句不是把前导0的情况过滤了嘛

panic 2022-08-24 17:51

可以看我的答案，需要判断如果单词长度大于1，并且开头是0，则直接返回false，if (words[row].size()>1 && col==words[row].size()-1 && letterMap[words[row][col]-‘A’]==0) return false;

class Solution {
public:
    vector<string> words;
    vector<bool> usedNum;
    vector<int> letterMap;
    int len=0;
    bool dfs(int col,int row,int c){
        if (col==len){
            return c==0;
        }
        if (row==words.size()){
            int sum=c;
            for (int i=0;i<words.size()-1;i++)
                if (words[i].size()>col) sum+=letterMap[words[i][col]-'A'];
            if (sum%10!=letterMap[words.back()[col]-'A']) return false;
            return dfs(col+1,0,sum/10);
        }
        if (words[row].size()>1 && col==words[row].size()-1 && letterMap[words[row][col]-'A']==0) return false;
        if (col>=words[row].size() || letterMap[words[row][col]-'A']!=-1) return dfs(col,row+1,c);
        for (int num=0;num<=9;num++){
            if (usedNum[num] || (num==0 && words[row].size()>1 && col==words[row].size()-1)) continue;
            usedNum[num]=true;
            letterMap[words[row][col]-'A']=num;
            if (dfs(col,row+1,c)) return true;
            letterMap[words[row][col]-'A']=-1;
            usedNum[num]=false;
        }
        return false;
    }
    bool isSolvable(vector<string>& _words, string result) {
        words=_words;
        for (auto &s:words){
            reverse(s.begin(),s.end());
            len=max(len,(int)s.size());
        }
        reverse(result.begin(),result.end());
        if (len!=result.size() && len+1!=result.size()) return false;
        len=max(len,(int)result.size());
        words.push_back(result);
        usedNum=vector<bool>(10);
        letterMap=vector<int>(26,-1);
        return dfs(0,0,0);
    }
};