1307. Verbal Arithmetic Puzzle LeetCode Solution
In this guide, you will get 1307. Verbal Arithmetic Puzzle LeetCode Solution with the best time and space complexity. The solution to Verbal Arithmetic Puzzle problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Verbal Arithmetic Puzzle solution in C++
- Verbal Arithmetic Puzzle solution in Java
- Verbal Arithmetic Puzzle solution in Python
- Additional Resources
Problem Statement of Verbal Arithmetic Puzzle
Given an equation, represented by words on the left side and the result on the right side.
You need to check if the equation is solvable under the following rules:
Each character is decoded as one digit (0 – 9).
No two characters can map to the same digit.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on the left side (words) will equal to the number on the 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 = [“LEET”,”CODE”], result = “POINT”
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.
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.
Complexity Analysis
- Time Complexity:
- Space Complexity:
1307. Verbal Arithmetic Puzzle LeetCode Solution in C++
class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
usedDigit = vector<bool>(10);
words.push_back(result);
rows = words.size();
for (const string& word : words)
cols = max(cols, static_cast<int>(word.length()));
return dfs(words, 0, 0, 0);
}
private:
unordered_map<char, int> letterToDigit;
vector<bool> usedDigit;
int rows;
int cols;
bool dfs(vector<string>& words, int row, int col, int sum) {
if (col == cols)
return sum == 0;
if (row == rows)
return sum % 10 == 0 && dfs(words, 0, col + 1, sum / 10);
string word = words[row];
if (col >= word.length())
return dfs(words, row + 1, col, sum);
char letter = word[word.length() - col - 1];
int sign = row == rows - 1 ? -1 : 1;
if (const auto it = letterToDigit.find(letter);
it != letterToDigit.cend() &&
(it->second > 0 || col < word.length() - 1))
return dfs(words, row + 1, col, sum + sign * letterToDigit[letter]);
for (int digit = 0; digit < 10; ++digit)
if (!usedDigit[digit] && (digit > 0 || col + 1 < word.length())) {
letterToDigit[letter] = digit;
usedDigit[digit] = true;
if (dfs(words, row + 1, col, sum + sign * digit))
return true;
usedDigit[digit] = false;
letterToDigit.erase(letter);
}
return false;
}
};
/* code provided by PROGIEZ */1307. Verbal Arithmetic Puzzle LeetCode Solution in Java
class Solution {
public boolean isSolvable(String[] words, String result) {
rows = words.length + 1;
for (final String word : words)
cols = Math.max(cols, word.length());
cols = Math.max(cols, result.length());
return dfs(words, result, 0, 0, 0);
}
private Map<Character, Integer> letterToDigit = new HashMap<>();
private boolean[] usedDigit = new boolean[10];
private int rows = 0;
private int cols = 0;
private boolean dfs(String[] words, String result, int row, int col, int sum) {
if (col == cols)
return sum == 0;
if (row == rows)
return sum % 10 == 0 && dfs(words, result, 0, col + 1, sum / 10);
String word = row == rows - 1 ? result : words[row];
if (col >= word.length())
return dfs(words, result, row + 1, col, sum);
char letter = word.charAt(word.length() - col - 1);
int sign = row == rows - 1 ? -1 : 1;
if (letterToDigit.containsKey(letter) &&
(letterToDigit.get(letter) > 0 || col < word.length() - 1))
return dfs(words, result, row + 1, col, sum + sign * letterToDigit.get(letter));
for (int digit = 0; digit < 10; ++digit)
if (!usedDigit[digit] && (digit > 0 || col < word.length() - 1)) {
letterToDigit.put(letter, digit);
usedDigit[digit] = true;
if (dfs(words, result, row + 1, col, sum + sign * letterToDigit.get(letter)))
return true;
usedDigit[digit] = false;
letterToDigit.remove(letter);
}
return false;
}
}
// code provided by PROGIEZ1307. Verbal Arithmetic Puzzle LeetCode Solution in Python
class Solution:
def isSolvable(self, words: list[str], result: str) -> bool:
words.append(result)
rows = len(words)
cols = max(map(len, words))
letterToDigit = {}
usedDigit = [False] * 10
def dfs(row: int, col: int, summ: int) -> bool:
if col == cols:
return summ == 0
if row == rows:
return summ % 10 == 0 and dfs(0, col + 1, summ // 10)
word = words[row]
if col >= len(word):
return dfs(row + 1, col, summ)
letter = word[~col]
sign = -1 if row == rows - 1 else 1
if letter in letterToDigit and (
letterToDigit[letter] > 0 or col < len(word) - 1):
return dfs(row + 1, col, summ + sign * letterToDigit[letter])
for digit, used in enumerate(usedDigit):
if not used and (digit > 0 or col < len(word) - 1):
letterToDigit[letter] = digit
usedDigit[digit] = True
if dfs(row + 1, col, summ + sign * digit):
return True
usedDigit[digit] = False
if letter in letterToDigit:
del letterToDigit[letter]
return False
return dfs(0, 0, 0)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.