宝宝也能看懂的 leetcode 周赛 - 169 - 4

2020/1/4 5:21:16

编程Tag： javascript 前端 算法 程序员 LeetCode

本文主要是介绍宝宝也能看懂的 leetcode 周赛 - 169 - 4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1307. Verbal Arithmetic Puzzle

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

这里是第 169 期的第 4 题，也是题目列表中的第 1307 题 -- 『Verbal Arithmetic Puzzle』

题目描述

Given an equation, represented by words on left side and the result on right side.

You need to check if the equation is solvable under the following rules:

  • Each character is decoded as one digit (0 - 9).
  • Every pair of different characters they must map to different digits.
  • Each words[i] and result are decoded as one number without leading zeros.
  • Sum of numbers on left side (words) will equal to the number on right side (result).

Return True if the equation is solvable otherwise return False.

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["THIS","IS","TOO"], result = "FUNNY"
Output: true

Example 4:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false

Constraints:

  • 2 <= words.length <= 5
  • 1 <= words[i].length, result.length <= 7
  • words[i], result contains only upper case English letters.
  • Number of different characters used on the expression is at most 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 即可。但是如何同时来记录上面用到的 charVal、usedVal 和 leadChar 呢？

这里首先我们看一下，'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% 了。

总结

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

相关链接



这篇关于宝宝也能看懂的 leetcode 周赛 - 169 - 4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程