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+,仍旧是十分慢。
看到上面的时间我意识到,这个思路是有问题的。我一定是忽略了什么非常重要的信息。回头再看看题目中等式这个条件,想想加法的运算过程,恍然大悟,其实我们只需要按照加法的运算顺序来判断即可。过程如下:
- 我们遍历所有因子,检查占据着个位的字符。如果它已经被赋值了,则直接使用,如果没有被赋值,则猜测一个可能值。
- 求和后我们便能计算出结果中的个位的数值。接下来判断结果中占据着个位的字符,看看是否符合我们的要求。并且注意,这里的求和进位一定不要忘了。
- 依次处理十位、百位等所有的位置,直到我们超过了结果字符串的长度。那么意味着我们找到了一个符合要求的解,也就是等式可以成立。如果过程中有任何不符合要求的地方,都直接跳出以避免不必要的递归判断。
有了这个思路后,我们可以发现整个尝试的过程变得理性了很多,不再像是完全盲目的尝试。并且大多数不合理的尝试都可以在较早的时候被及时终止。于是我们来做代码实现。
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% 了。
这道题中,对于优化过程的思路进行了较多的分析。也给出了我从十分辣眼睛的代码到最后方案的完整过程。其中比较关键的一点是,当意识到情况不对的时候,重新看条件并整理思路,可能比仍旧在旧思路上死磕更好。