LEETCODE 1307. Verbal Arithmetic Puzzle 解题思路分析

题目大意:

口算难题

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

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

  • 每个字符都会被解码成一位数字(0 – 9)。
  • 每对不同的字符必须映射到不同的数字。
  • 每个 words[i] 和 result 都会被解码成一个没有前导零的数字。
  • 左侧数字之和(words)等于右侧数字(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 = ["THIS","IS","TOO"], result = "FUNNY"
输出:true

示例 4:

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

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1307

解题思路分析:

本题是一道Hard级别的难题,看完题目之后,第一个想法就是暴力解,因为最多只有10种字符,我们分别用0-9表示每种字符,查看是否存在一种左侧数字之和等于右侧数字的方案即可。解题步骤大致如下:

  1. 先遍历题目给出的words数组以及result字符串,查看它们都含有哪些大写字母。我们使用一个长度为26的一位boolean型数组来记录出现过的字母,数组下标0-25分别对应字母a-z。如果存在该字母,数组对应下标的值更新为true。
  2. 使用递归方法为每一个字母赋值,赋值范围是0-9中的一个数字,递归函数的参数需要另一个boolean型数组来记录使用过的数字。递归的顺序为字母a到字母z。递归时,首先查看当前字母是否在words数组以及result字符串中出现过,如果没出现过,那么不需要赋值,直接递归到下一层子方法,查看下一个字母。反之如果出现过,那么我们则需要给当前字母赋值,我们循环0-9,使用每一个还没有使用过的数字来给当前字母赋值,赋值后,将当前数字标记为已经使用过,然后递归到下一层子问题为下一个字母赋值。这里需要注意一点,题目要求每个字符串的首字符不能以0开头,因此,如果当前字母是某个字符串的首字符时,不能赋值为0。
  3. 递归的结束条件为,当递归到字母z,并且赋值完成之后,说明所有字母都赋值成功,此时,将等式左边的每个单词以及等式右边的结果字符串,按照赋值的数值转化成数字,即可判断其是否相等。

实现代码:

boolean[] has=new boolean[26]; // 记录包含哪些字符
boolean[] firstChar = new boolean[26]; // 记录哪些字符是字符串的首字符
public boolean isSolvable(String[] words, String result) {
    // 遍历每个单词
    for(String w : words){
        // 查看单词包含哪些字符
        for(int i=0;i<w.length();i++){
            int index=w.charAt(i)-'A';
            has[index]=true;
            if(i==0) firstChar[index]=true;
        }
    }
    // 遍历result字符串每个字符,查看包含哪些字符
    for(int i=0;i<result.length();i++){
        int index=result.charAt(i)-'A';
        has[index]=true;
        if(i==0) firstChar[index]=true;
    }
    // 记录字符对应的数字(下标0-25代表字符A-Z)
    int[] num = new int[26];
    // 默认为-1
    Arrays.fill(num, -1);
    // 递归赋值
    return dfs(words, result, num, 0, new boolean[10]);
}
// words为题目给出的等式左边所有字符串
// result为题目给出的等式右边字符串
// num为字符对应的数字
// letter为当前字符
// numUsed为使用过的数字
// 返回值为是否能够使等式相等
boolean dfs(String[] words, String result, int[] num, int letter, boolean[] numUsed){
    if(letter==26){ // 26个字母都赋值完成时
        int r=0; // 计算result对应的数字
        for(int i=0;i<result.length();i++){
            r= r*10+num[result.charAt(i)-'A'];
        }
        int sum=0; // 计算等式左边所有字符串对应数字之和
        for(String w : words){
            int n=0;
            for(int i=0;i<w.length();i++){
                n= n*10+num[w.charAt(i)-'A'];
            }
            sum+=n;
        }
        // 返回等式两边是否相等
        return sum==r;
    }
    // 如果当前字母是题目给出的字符
    if(has[letter]){
        // 尝试从0-9循环赋值
        for(int j=0;j<10;j++){
            // 如果当前数字已经被使用过,跳过
            if(numUsed[j]) continue;
            // 如果当前数字是0,并当前字符是某个字符串的首字符,跳过
            if(j==0&&firstChar[letter]) continue;
            // 将当前字母赋值为当前数字
            num[letter]=j;
            // 记录当前数字已经使用过
            numUsed[j]=true;
            // 递归到下一个字母
            if(dfs(words,result,num,letter+1,numUsed)) return true;
            num[letter]=-1;
            numUsed[j]=false;
        }
    }else{
        // 如果当前字母不是题目给出的字符
        // 递归到下一个字母
        return dfs(words,result,num,letter+1,numUsed);
    }
    return false;
}

本题解法执行时间为1337ms。

Runtime: 1371 ms, faster than 24.04% of Java online submissions for Verbal Arithmetic Puzzle.

Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Verbal Arithmetic Puzzle.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1307-verbal-arithmetic-puzzle-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。