Skip to content

Latest commit

 

History

History
341 lines (269 loc) · 14.1 KB

1307.md

File metadata and controls

341 lines (269 loc) · 14.1 KB

1307. 口算难题

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 169 期的第 4 题,也是题目列表中的第 1307 题 -- 『口算难题』

题目描述

给你一个方程,左边用 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

官方难度

HARD

解决思路

题目的内容为,给定一组字符串作为因子和一个结果字符串,字符串中都是英文大写字母。字符串中的每个字符代表了一个数字,不允许两个不同的字符代表同一个数字,也不允许两个相同的字符代表不同的数字。并且每一个字符串开头的第一个字符不可以代表 0。最终,期望这一组因子的数字求和需要等于结果,如果能实现的话返回 true,否则返回 false。结合上文中的例子可以更清晰的理解题目的意思。

乍一看感觉题目需求还挺简单,但是解题思路一脸懵逼。思考了一会,觉得似乎没有什么特殊的数学方法来处理,于是只能依赖计算机强大的计算能力来尝试每一种可能。最终看是否能找到符合要求的解。

既然决定了要暴力莽一把,那么一种非常常见的莽法就涌上心头,即基于深度优先遍历来更快的探查到每一个可能解,并结合递归来实现回溯。

于是撸起猪蹄子,揉揉猪鼻子,奥利给,淦了!

直接方案

基于上述思路,我们用一个 Map 来记录字符和它对应的数字,用一个数组来记录所有不同的字符,用一个 Set 来记录我们已经使用过的数字。接下来需要做的,只是遍历这个数组中的字符,给每个字符尝试枚举所有的当前还未使用的值。最后测试一下等式是否成立即可。

以下代码比较辣眼睛,可能会有损你的视力,请在坚强的自己的陪同下,一起鄙视我。 T_T

const convertVal = (str, charVal) => {
  let val = 0;
  for (let i = 0; i < str.length; ++i) {
    val = val * 10 + charVal.get(str[i]);
  }
  return val;
};
const isSolvable = (words, result) => {
  const charVal = new Map();
  const chars = [];
  for (const char of result) {
    !charVal.has(char) && chars.push(char) && charVal.set(char, -1);
  }
  for (const word of words) {
    for (const char of word) {
      !charVal.has(char) && chars.push(char) && charVal.set(char, -1);
    }
  }
  if (charVal.size > 10) return false;
  const usedVal = new Set();
  return helper(0);

  function helper(idx) {
    if (idx === charVal.size) return check();
    const char = chars[idx];
    for (let i = 0; i <= 9; ++i) {
      if (usedVal.has(i) || (idx === 0 && i === 0)) continue;
      charVal.set(char, i);
      usedVal.add(i);
      if (helper(idx +1)) return true;
      usedVal.delete(i);
    }
    return false;
  }

  function check() {
    let sum = 0;
    for (const word of words) {
      if (charVal[word[0]] === 0) return false;
      sum += convertVal(word, charVal)
    }
    return sum === convertVal(result, charVal);
  }
};

为什么这么辣眼睛还要放出来?因为宝宝真实(此处应有掌声) >.<

这确实是我提交的第一次代码,Acceped 了,但是时间是 8000+ms,这座城又多了只伤心的猪。 T_T

优化

上述代码基本尝试了各种可能,所以结果才那么慢。那么我们的优化思路有两个方向:

  • 减少基础尝试的链条长度
  • 提前终止不必要的尝试

前者除了能降低调用栈的深度,减少空间使用之外,更是由于分支的铺开速度是接近指数级的,所以能有效的提升性能。后者在前者的基础上,可以一定程度上的提高性能。

那么我们回看题目描述,满足要求的因子和结果这是一个等式。看到这里其实我们可以想到一件事情,我们不用针对所有字符枚举出所有的可能值。因为如果等式成立的话,其中某一项的值是可以基于其他项目的值计算出来的。基于此,我们便能减少基础尝试链条的长度。另外由于题目不允许数字出现先导 0,即第一个字符不能对应 0,所以我们可以用这个条件提前终止不必要的尝试。

以下代码把一个因子从基础尝试链条中去掉了,并且在初始化的时候记录了所有字符串的第一个字符用于判断先导 0。

const convertVal = (str, charVal) => {
  let val = 0;
  for (let i = 0; i < str.length; ++i) {
    val = val * 10 + charVal.get(str[i]);
  }
  return val;
};

const isSolvable = (words, result) => {
  const charVal = new Map();
  const usedVal = new Set();
  const lastWord = words[words.length - 1];
  const leadChar = new Set([result[0], lastWord[0]]);
  let chars = result;
  for (let i = 0; i < words.length - 1; ++i) {
    chars += words[i];
    leadChar.add(words[i][0]);
  }
  return helper(0);

  function helper(idx) {
    if (idx === chars.length) return check();
    const char = chars[idx];
    if (charVal.has(char)) return helper(idx + 1);
    for (let i = 0; i <= 9; ++i) {
      if (usedVal.has(i) || (i === 0 && leadChar.has(char))) continue;
      usedVal.add(i);
      charVal.set(char, i);
      if (helper(idx + 1)) return true;
      charVal.delete(char);
      usedVal.delete(i);
    }
    return false;
  }

  function check() {
    let sum = convertVal(result, charVal);
    for (let i = 0; i < words.length - 1; ++i) {
      sum -= convertVal(words[i], charVal);
      if (sum < 0) return false;
    }
    sum = sum.toString().split('');
    if (sum.length !== lastWord.length) return false;
    for (let i = 0; i < sum.length; ++i) {
      if (charVal.has(lastWord[i]) && +sum[i] !== charVal.get(lastWord[i])) return false;
    }
    return true;
  }
};

这段代码提交后时间来到了 5000ms+,仍旧是十分慢。

换个思路

看到上面的时间我意识到,这个思路是有问题的。我一定是忽略了什么非常重要的信息。回头再看看题目中等式这个条件,想想加法的运算过程,恍然大悟,其实我们只需要按照加法的运算顺序来判断即可。过程如下:

  1. 我们遍历所有因子,检查占据着个位的字符。如果它已经被赋值了,则直接使用,如果没有被赋值,则猜测一个可能值。
  2. 求和后我们便能计算出结果中的个位的数值。接下来判断结果中占据着个位的字符,看看是否符合我们的要求。并且注意,这里的求和进位一定不要忘了。
  3. 依次处理十位、百位等所有的位置,直到我们超过了结果字符串的长度。那么意味着我们找到了一个符合要求的解,也就是等式可以成立。如果过程中有任何不符合要求的地方,都直接跳出以避免不必要的递归判断。

有了这个思路后,我们可以发现整个尝试的过程变得理性了很多,不再像是完全盲目的尝试。并且大多数不合理的尝试都可以在较早的时候被及时终止。于是我们来做代码实现。

const isSolvable = (words, result) => {
  const charVal = new Map();
  const usedVal = new Set();
  const leadChar = new Set(result[0]);
  const WORDS_COUNT = words.length;
  const MAX_WORD_LEN = result.length;

  for (let i = 0; i < WORDS_COUNT; ++i) {
    if (words[i].length > MAX_WORD_LEN) return false;
    leadChar.add(words[i][0]);
  }
  return helper(1, 0, 0);

  function helper(digit, wordIdx, carry) {
    if (digit > MAX_WORD_LEN) return true;

    if (wordIdx === WORDS_COUNT) {
      const resultNum = carry % 10;
      const resultChar = result[MAX_WORD_LEN - digit];
      const isUsed = charVal.has(resultChar);
      if (
        (!isUsed && usedVal.has(resultNum))
        || (isUsed && charVal.get(resultChar) !== resultNum)
        || (resultNum === 0 && leadChar.has(resultChar))
      ) return false;
      usedVal.add(resultNum);
      charVal.set(resultChar, resultNum);
      if (helper(digit + 1, 0, (carry - resultNum) / 10)) return true;
      !isUsed && usedVal.delete(resultNum) && charVal.delete(resultChar);
      return false;
    }

    const idx = words[wordIdx].length - digit;
    if (idx < 0) return helper(digit, wordIdx + 1, carry);
    const char = words[wordIdx][idx];
    if (charVal.has(char)) return helper(digit, wordIdx + 1, carry + charVal.get(char));
    for (let i = 0; i < 10; ++i) {
      if (usedVal.has(i) || (i === 0 && leadChar.has(char))) continue;
      usedVal.add(i);
      charVal.set(char, i);
      if (helper(digit, wordIdx + 1, carry + i)) return true;
      usedVal.delete(i);
      charVal.delete(char);
    }

    return false;
  }
};

这段代码相比之前的代码是不是没有那么辣眼睛了。当然,从时间上来看我们的思路也得到了回报。跑出了 112ms 有了数量级的提升,暂时 beats 了 100%。

再优化

已经 beats 100% 了为什么还要再继续尝试优化呢?因为上述 3 段代码中,都使用到了 1 个 Map 和 2 个 Set。而我觉得其实都可以去掉。转换为只使用一个定长的 Uint8Array 来记录我们需要的数据。那么现在需要解决的问题就是,我们如何来记录这些数据。

看了一下题目的限制条件,每个字符一定是英文大写字符,也就是只会从 'A' 到 'Z'。这里第一反应就是取字符的 char code 即可。但是如何同时来记录上面用到的 charValusedValleadChar 呢?

这里首先我们看一下,'A' 的 char code 是 65,也就是说如果不使用减去偏移量的方式,在满足了 charVal 的存储需求后,我们的定长数组中还存在着前面 65 个空缺。这时候可以想到,我们可以把 usedVal 的需求,也就是已经使用的数值也记录在里面,它们将占据 [0, 9] 这一段范围,也就是还剩下 [10, 64] 这么多空缺。这一大段完全够 leadChar 来使用了。具体储存规则如下:

  • 基于 Uint8Array 的定长数组长度为 91,因为 'Z' 的 char code 是 90。
  • 使用 10 作为数组的初始值,因为默认的 0 在我们的取值范围 [0, 9] 之内。
  • 使用下标范围 [0, 9] 来标识已经被使用的数值。
  • 使用下标范围 [65, 90] 来记录每个字符对应的数字值。
  • 使用下标范围 [35, 60] 来标识占据着先导 0 位置的字符,这个范围是每个字符 char code 减去偏移量 30。

当然,上述规则的偏移量可以自行设定。只需要 3 个范围不重叠即可。具体代码如下。

const isSolvable = (words, result) => {
  const WORDS_COUNT = words.length;
  const MAX_WORD_LEN = result.length;
  const OFFSET = 30;
  const INIT_VAL = 10;
  const charVal = new Uint8Array(91).fill(INIT_VAL);

  charVal[result.charCodeAt(0) - OFFSET] = 1;
  for (let i = 0; i < WORDS_COUNT; ++i) {
    if (words[i].length > MAX_WORD_LEN) return false;
    charVal[words[i].charCodeAt(0) - OFFSET] = 1;
  }
  return helper(1, 0, 0);

  function helper(digit, wordIdx, carry) {
    if (digit > MAX_WORD_LEN) return true;

    if (wordIdx === WORDS_COUNT) {
      const resultNum = carry % 10;
      const resultCharCode = result.charCodeAt(MAX_WORD_LEN - digit);
      const isUsed = charVal[resultCharCode] !== INIT_VAL;
      if (
        (!isUsed && charVal[resultNum] === 1)
        || (isUsed && charVal[resultCharCode] !== resultNum)
        || (resultNum === 0 && charVal[resultCharCode - OFFSET] === 1)
      ) return false;
      charVal[resultNum] = 1;
      charVal[resultCharCode] = resultNum;
      if (helper(digit + 1, 0, (carry - resultNum) / 10)) return true;
      !isUsed && (charVal[resultNum] = INIT_VAL) && (charVal[resultCharCode] = INIT_VAL);
      return false;
    }

    const idx = words[wordIdx].length - digit;
    if (idx < 0) return helper(digit, wordIdx + 1, carry);
    const charCode = words[wordIdx].charCodeAt(idx);
    if (charVal[charCode] !== INIT_VAL) return helper(digit, wordIdx + 1, carry + charVal[charCode]);
    for (let i = 0; i < 10; ++i) {
      if (charVal[i] !== INIT_VAL || (i === 0 && charVal[charCode - OFFSET] !== INIT_VAL)) continue;
      charVal[i] = 1;
      charVal[charCode] = i;
      if (helper(digit, wordIdx + 1, carry + i)) return true;
      charVal[i] = INIT_VAL;
      charVal[charCode] = INIT_VAL;
    }

    return false;
  }
};

这段代码最终跑到了 68ms 的时间,当然也替代了上面的代码暂时 beats 100% 了。

总结

这道题中,对于优化过程的思路进行了较多的分析。也给出了我从十分辣眼睛的代码到最后方案的完整过程。其中比较关键的一点是,当意识到情况不对的时候,重新看条件并整理思路,可能比仍旧在旧思路上死磕更好。

相关链接

我的微信公众号:张小猪粉鼻子