LeetCode 题解工作台
口算难题
给你一个方程，左边用 words 表示，右边用 result 表示。 你需要根据以下规则检查方程是否可解： 每个字符都会被解码成一位数字（0 - 9）。 每对不同的字符必须映射到不同的数字。 每个 words[i] 和 result 都会被解码成一个没有前导零的数字。 左侧数字之和（ words ）…
4
题型
3
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
class Solution: def isAnyMapping(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一个方程，左边用 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 <= 51 <= words[i].length, results.length <= 7words[i], result只含有大写英文字母- 表达式中使用的不同字符数最大为 10
解题思路
方法一
class Solution:
def isAnyMapping(
self, words, row, col, bal, letToDig, digToLet, totalRows, totalCols
):
# If traversed all columns.
if col == totalCols:
return bal == 0
# At the end of a particular column.
if row == totalRows:
return bal % 10 == 0 and self.isAnyMapping(
words, 0, col + 1, bal // 10, letToDig, digToLet, totalRows, totalCols
)
w = words[row]
# If the current string 'w' has no character in the ('col')th index.
if col >= len(w):
return self.isAnyMapping(
words, row + 1, col, bal, letToDig, digToLet, totalRows, totalCols
)
# Take the current character in the variable letter.
letter = w[len(w) - 1 - col]
# Create a variable 'sign' to check whether we have to add it or subtract it.
if row < totalRows - 1:
sign = 1
else:
sign = -1
# If we have a prior valid mapping, then use that mapping.
# The second condition is for the leading zeros.
if letter in letToDig and (
letToDig[letter] != 0
or (letToDig[letter] == 0 and len(w) == 1)
or col != len(w) - 1
):
return self.isAnyMapping(
words,
row + 1,
col,
bal + sign * letToDig[letter],
letToDig,
digToLet,
totalRows,
totalCols,
)
# Choose a new mapping.
else:
for i in range(10):
# If 'i'th mapping is valid then select it.
if digToLet[i] == "-" and (
i != 0 or (i == 0 and len(w) == 1) or col != len(w) - 1
):
digToLet[i] = letter
letToDig[letter] = i
# Call the function again with the new mapping.
if self.isAnyMapping(
words,
row + 1,
col,
bal + sign * letToDig[letter],
letToDig,
digToLet,
totalRows,
totalCols,
):
return True
# Unselect the mapping.
digToLet[i] = "-"
if letter in letToDig:
del letToDig[letter]
# If nothing is correct then just return false.
return False
def isSolvable(self, words, result):
# Add the string 'result' in the list 'words'.
words.append(result)
# Initialize 'totalRows' with the size of the list.
totalRows = len(words)
# Find the longest string in the list and set 'totalCols' with the size of that string.
totalCols = max(len(word) for word in words)
# Create a HashMap for the letter to digit mapping.
letToDig = {}
# Create a list for the digit to letter mapping.
digToLet = ["-"] * 10
return self.isAnyMapping(
words, 0, 0, 0, letToDig, digToLet, totalRows, totalCols
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of backtracking and its application in solving constraint satisfaction problems.
- question_mark
Candidates should demonstrate awareness of pruning techniques to optimize the search.
- question_mark
The ability to handle edge cases such as leading zeros and duplicate digit mappings is crucial.
常见陷阱
外企场景- error
Not pruning effectively, leading to an inefficient search that takes too long to complete.
- error
Assigning the same digit to multiple characters, violating the problem's constraints.
- error
Failing to handle leading zeros in the result or words, which can invalidate the solution.
进阶变体
外企场景- arrow_right_alt
Allowing the equation to involve subtraction or multiplication instead of addition.
- arrow_right_alt
Reducing the number of words and increasing the result's length to test algorithm efficiency.
- arrow_right_alt
Introducing additional constraints, such as limiting the number of digits or allowing for negative digits.