1307-口算难题(Verbal Arithmetic Puzzle)

原文链接: https://leetcode-cn.com/problems/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 contain only uppercase English letters.
The number of different characters used in the expression is at most 10.

中文题目

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

通过代码

高赞题解

解题思路：

模拟合并同类项

比如 SIX + SEVEN + SEVEN = TWENTY ，第 0 阶段的方程式为：X + 2N + inc - Y = 0
根据数位列出各个方程，有几位数字，就能列出几个方程

因为题目的单词长度最多 8 个字母，所以最多可以列 8 个方程
回溯时根据每个方程阶段性判断剪枝
1. 进入个位的方程时，只对涉及的几个字母进行判断，这样就避免了很多无用计算，达到剪枝效果
2. 升入十位后，只对新出现的字母判断，依旧是剪枝状态
3. 如果通过就进入下一阶段，如果全部失败，就退回到上一阶段

举例说明：

比如：
SEND + MORE == MONEY
0位：D + E + inc - Y = 0
1位：N + R + inc - (E) = 0
2位：(E) + O + inc - (N) = 0
3位：S + M + inc - (O) = 0
4位：inc - (M) = 0

inc 为进位，初始为 0
等于 0 的意思为，个位为 0 即可通过。十位作为进位进入下一阶段

第 0 阶段，先枚举 DEY 三个字母，方程为 D+E-Y 的结果，个位为 0 就好，十位就进位到下一阶段
然后第 1 阶段，因为 E 再上一个阶段确定了，这个阶段确定 NR ，判断的方程用 N + R + 进位 - E。
如果不符合了，就原路回溯回去。
一路到底就返回结果。

执行流程如果想不明白，可以打开输出的注释，在 vs 里打断点看看

<,,,,,,>

实际操作

首先要把初始数据转换成分阶段的数据，因为单词最多 8 个字母，所以分成 8 个阶段，使用vector<vector<int>> equation(8, vector<int>(26, 0));来保存每个阶段有哪些字母，用了几个，是加还是减。
然后根据上面的数据，再找出每个阶段需要确定的字母，前个阶段确定过的字母，这个阶段不用改，只确定新增的。使用vector<vector<char>> chars(8, vector<char>());来保存。
还需要一些变量来保存查询中的状态。比如 0-9 这 10 个数字哪些使用过了 ne，字母被确定了要当做哪个数字 en，还有第一位不能为 0 的zeroFlag。
dfs中，ne 和 en 回溯。然后 lv 是记录现在哪个阶段，idx 是当前阶段确定第几个字母。

代码：

[]
// 检查当前阶段方程是否成立，以及更新进位inc
bool check(vector<vector<int>>& eq, int lv, vector<int>& en, int& inc)
{
	auto& cur_eq = eq[lv];
	int sum = inc;
	for (int i = 0; i < cur_eq.size(); i++)
	{
		sum += cur_eq[i] * en[i];
	}
	inc = sum / 10;
	return (sum % 10 == 0);
}

void dfs(vector<vector<int>>& eq, vector<vector<char>>& chars, int lv, int idx, int inc, vector<char>& ne, vector<int>& en, vector<bool>& zeroFlag, bool& ans)
{
	if (ans) return;
	if (idx == chars[lv].size())
	{
		//{	// 输出 log
		//	for (size_t i = 0; i < 26; i++)
		//	{
		//		if (en[i] == -1) continue;
		//		char c = i + 'A';
		//		cout << c << ": " << en[i] << "\t";
		//	}
		//	int temp = inc;
		//	string str = (check(eq, lv, en, temp)) ? "check success!" : "check failed";
		//	cout << str << endl;
		//}

		if (!check(eq, lv, en, inc)) return; // 检查方程
		ans = (lv == 7);
		if (ans) return;

		dfs(eq, chars, lv + 1, 0, inc, ne, en, zeroFlag, ans); // 检查成功，升阶段
	}

	if (idx < 0 || idx >= chars[lv].size()) return;
	char c = chars[lv][idx];
	for (int n = 0; n < 10; n++)
	{
		if (ne[n] != 'a') continue;
		if (n == 0 && zeroFlag[c - 'A']) continue;

		en[c - 'A'] = n; // 字母对应的数字
		ne[n] = c; // 数字对应的字母（作用相当于数字是否used）
		int tempInc = inc;

		dfs(eq, chars, lv, idx + 1, inc, ne, en, zeroFlag, ans);

		en[c - 'A'] = -1; // 回溯，把状态改回来
		ne[n] = 'a';
		inc = tempInc;
	}
}

bool isSolvable(vector<string>& words, string result)
{
	vector<char> ne(10, 'a');
	vector<int> en(26, -1);
	vector<bool> zeroFlag(26, false);
	vector<vector<int>> equation(8, vector<int>(26, 0));
	vector<vector<char>> chars(8, vector<char>());

	words.push_back(result);
	for (size_t j = 0; j < words.size(); j++)
	{
		auto w = words[j];
		zeroFlag[w[0] - 'A'] = true;
		size_t d = 0;
		for (size_t i = w.size() - 1; i < w.size(); i--)
		{
			equation[d++][w[i] - 'A'] += (j == words.size() - 1) ? -1 : 1;
		}
	}
	unordered_set<char> us;
	for (size_t d = 0; d < 8; d++)
	{
		for (int i = 0; i < equation[d].size(); i++)
		{
			if (equation[d][i] == 0) continue;
			char c = i + 'A';
			if (us.count(c) != 0) continue;
			chars[d].push_back(c);
			us.insert(c);
		}
	}

	bool ans = false;
	dfs(equation, chars, 0, 0, 0, ne, en, zeroFlag, ans);
	return ans;
}

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

统计信息

通过次数	提交次数	AC比率
1887	5709	33.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途