| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2250 |
第 169 场周赛 Q4 |
|
给你一个方程，左边用 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
)class Solution {
private boolean isAnyMapping(List<String> words, int row, int col, int bal,
HashMap<Character, Integer> letToDig, char[] digToLet, int totalRows, int 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
&& isAnyMapping(
words, 0, col + 1, bal / 10, letToDig, digToLet, totalRows, totalCols));
}
String w = words.get(row);
// If the current string 'w' has no character in the ('col')th index.
if (col >= w.length()) {
return isAnyMapping(words, row + 1, col, bal, letToDig, digToLet, totalRows, totalCols);
}
// Take the current character in the variable letter.
char letter = w.charAt(w.length() - 1 - col);
// Create a variable 'sign' to check whether we have to add it or subtract it.
int sign = (row < totalRows - 1) ? 1 : -1;
// If we have a prior valid mapping, then use that mapping.
// The second condition is for the leading zeros.
if (letToDig.containsKey(letter)
&& (letToDig.get(letter) != 0 || (letToDig.get(letter) == 0 && w.length() == 1)
|| col != w.length() - 1)) {
return isAnyMapping(words, row + 1, col, bal + sign * letToDig.get(letter), letToDig,
digToLet, totalRows, totalCols);
} else {
// Choose a new mapping.
for (int i = 0; i < 10; i++) {
// If 'i'th mapping is valid then select it.
if (digToLet[i] == '-'
&& (i != 0 || (i == 0 && w.length() == 1) || col != w.length() - 1)) {
digToLet[i] = letter;
letToDig.put(letter, i);
// Call the function again with the new mapping.
if (isAnyMapping(words, row + 1, col, bal + sign * letToDig.get(letter),
letToDig, digToLet, totalRows, totalCols)) {
return true;
}
// Unselect the mapping.
digToLet[i] = '-';
letToDig.remove(letter);
}
}
}
// If nothing is correct then just return false.
return false;
}
public boolean isSolvable(String[] wordsArr, String result) {
// Add the string 'result' in the list 'words'.
List<String> words = new ArrayList<>();
for (String word : wordsArr) {
words.add(word);
}
words.add(result);
int totalRows = words.size();
// Find the longest string in the list and set 'totalCols' with the size of that string.
int totalCols = 0;
for (String word : words) {
if (totalCols < word.length()) {
totalCols = word.length();
}
}
// Create a HashMap for the letter to digit mapping.
HashMap<Character, Integer> letToDig = new HashMap<>();
// Create a char array for the digit to letter mapping.
char[] digToLet = new char[10];
for (int i = 0; i < 10; i++) {
digToLet[i] = '-';
}
return isAnyMapping(words, 0, 0, 0, letToDig, digToLet, totalRows, totalCols);
}
}class Solution {
public:
bool isAnyMapping(vector<string>& words, int row, int col, int bal, unordered_map<char, int>& letToDig,
vector<char>& digToLet, int totalRows, int 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 && isAnyMapping(words, 0, col + 1, bal / 10, letToDig, digToLet, totalRows, totalCols));
}
string w = words[row];
// If the current string 'W' has no character in the ('COL')th index.
if (col >= w.length()) {
return isAnyMapping(words, row + 1, col, bal, letToDig, digToLet, totalRows, totalCols);
}
// Take the current character in the variable letter.
char letter = w[w.length() - 1 - col];
// Create a variable 'SIGN' to check whether we have to add it or subtract it.
int sign;
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 (letToDig.count(letter) && (letToDig[letter] != 0 || (letToDig[letter] == 0 && w.length() == 1) || col != w.length() - 1)) {
return isAnyMapping(words, row + 1, col, bal + sign * letToDig[letter],
letToDig, digToLet, totalRows, totalCols);
}
// Choose a new mapping.
else {
for (int i = 0; i < 10; i++) {
// If 'i'th mapping is valid then select it.
if (digToLet[i] == '-' && (i != 0 || (i == 0 && w.length() == 1) || col != w.length() - 1)) {
digToLet[i] = letter;
letToDig[letter] = i;
// Call the function again with the new mapping.
bool x = isAnyMapping(words, row + 1, col, bal + sign * letToDig[letter],
letToDig, digToLet, totalRows, totalCols);
if (x == true) {
return true;
}
// Unselect the mapping.
digToLet[i] = '-';
if (letToDig.find(letter) != letToDig.end()) {
letToDig.erase(letter);
}
}
}
}
// If nothing is correct then just return false.
return false;
}
bool isSolvable(vector<string>& words, string result) {
// Add the string 'RESULT' in the vector 'WORDS'.
words.push_back(result);
int totalRows;
int totalCols;
// Initialize 'TOTALROWS' with the size of the vector.
totalRows = words.size();
// Find the longest string in the vector and set 'TOTALCOLS' with the size of that string.
totalCols = 0;
for (int i = 0; i < words.size(); i++) {
// If the current string is the longest then update 'TOTALCOLS' with its length.
if (totalCols < words[i].size()) {
totalCols = words[i].size();
}
}
// Create a HashMap for the letter to digit mapping.
unordered_map<char, int> letToDig;
// Create a vector for the digit to letter mapping.
vector<char> digToLet(10, '-');
return isAnyMapping(words, 0, 0, 0, letToDig, digToLet, totalRows, totalCols);
}
};