宝宝也能看懂的 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 即可。但是如何同时来记录上面用到的 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% 了。

总结

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

相关链接

Image placeholder
zhangleilei
未设置
  92人点赞

没有讨论,发表一下自己的看法吧

推荐文章
宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305.AllElementsinTwoBinarySearchTreesHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第2题,也是题目列表中的第13

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

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

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

1306.JumpGameIIIHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第3题,也是题目列表中的第1306题--『JumpGameIII』题目描述

我从来不觉得程序员是吃青春饭的!这里有169万份分析数据

阅读本文约需要5分钟程序员这个职业究竟可以干多少年,在中国这片神奇的土地上,很多人都说只能干到30岁,然后就需要转型。在很多面试中,问到应聘者未来的规划都能听到好些应聘都说程序员是个青春饭。因为,大多

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

LeetCode 刷题笔记

从AmazonOA高频题开始 总结每一道做过的题目,先总结一下思路,然后记录从中获取的新知识。题目顺序不是按照序号顺序的,而是题目在真实面试中出现的频率排序。由于之前已经做过一些了,所以那些题目暂时还

用 Rust 刷 leetcode 第二题

Problem Youaregiventwonon-emptylinkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredinre

用 Rust 刷 leetcode 第一题

problemGivenanarrayofintegers,return indices ofthetwonumberssuchthattheyadduptoaspecifictarget. Youm

用 Rust 刷 leetcode 第二题

ProblemYouaregiventwo non-empty linkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredin 

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

算法-最小栈-LeetCode155

题目最小栈设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈。push(x) --将元素x推入栈中。pop() --删除栈顶的元素。top() --获取栈顶元素。getMin

算法-下一个更大元素 I-LeetCode.496

题目下一个更大的元素I给定两个没有重复元素的数组 nums1和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数

Leetcode上最南的是哪道题?

大家伙想要找份好工作,刷题是一道绕不过的坎,Leetcode大家都很熟悉了,很多公司面试的时候会用上面的原题,今天我们就来看看这Leetcode上的题!首先依然通过利索的爬虫获取了Leetcode官网

全网最通俗易懂的Kafka入门

前言只有光头才能变强。文本已收录至我的GitHub仓库,欢迎Star:https://github.com/ZhongFuCheng3y/3y众所周知,消息队列的产品有好几种,这里我选择学习Kafka

终于有篇看的懂的 B 树文章了!

索引,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述完整。本文就来从头到尾介绍下数据库的索引。索引是一种数据结构,用于

一篇文章看懂,存储虚拟化在不同用例中的实践与优势

存储虚拟化是一种对物理存储资源进行抽象的技术,使其看起来像是一个集中的资源。虚拟化掩盖了管理内存、网络、服务器和存储中资源的复杂性。存储虚拟化运行在多个存储设备上,使它们看起来就像一个单一的存储池。这

DeepFakes进化版DeepNude惊现!一键“脱衣“,火到宕机

大数据文摘出品作者:蒋宝尚、赵伟人工智能的黑暗面能有多黑?这边DeepFake带来的余震还没有被平息,本周,又一AI偏门应用爆出,一键直接“脱掉”女性的衣服!海外媒体Motherboard测试图片显然

IEEE态度转变:解除对华为评审限制

大数据文摘出品作者:周素云、魏子敏IEEE的态度发生变化。今晨,IEEE电气电子工程师学会中国官网及官方公众号同时发出声明,表示IEEE向美国商务部要求就出口管制条例在IEEE出版活动的适用性做出说明

PHP跌出前十,铁打的 Python 连续3年第一:IEEE Spectrum 2019编程语言排行榜出炉

Python势头不减,依旧第一,而且进一步拉开了与其他语言的差距。这一结果,来自IEEESpectrum2019年度编程语言排行榜。这已经是Python连续3年保持第一。在Python之下,第二交椅的

IEEE官方禁止华为参与期刊审稿,当全球最大技术学术机构向政治弯腰

大数据文摘出品作者:魏子敏、宋欣仪5月29日,作为全球最大专业技术组织之一的IEEE(电气和电子工程师协会)被曝出,在发给会员的内部邮件中禁止华为员工作为旗下期刊杂志的编辑和审稿人。今天早晨,IEEE

beego 使用 coding 的 webhook 2.0 进行自动部署

beego使用coding的webhook2.0进行自动部署本文介绍beego在coding上如果使用webhook2.0进行自动部署。coding的webhook1.0教程coding平台端的设置这

PhpSpreadsheet 小教程

关于PhpSpreadsheet简单教程 今天遇到一个问题,涉及php与excel之间数据转换。之前一直用PHPExcel,他们的开发组不更新了。但是找到了PhpSpreadsheet。 一.介绍

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

etcd 在超大规模数据场景下的性能优化

作者|阿里云智能事业部高级开发工程师 陈星宇(宇慕)划重点etcd优化背景问题分析优化方案展示实际优化效果本文被收录在5月9日cncf.io官方blog中,链接:https://www.cncf.io