# 1307. Verbal Arithmetic Puzzle¶

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public: bool isSolvable(vector& words, string result) { usedDigit = vector(10); words.push_back(result); rows = words.size(); for (const string& word : words) cols = max(cols, static_cast(word.length())); return dfs(words, 0, 0, 0); } private: unordered_map letterToDigit; vector usedDigit; int rows; int cols; bool dfs(vector& 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 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 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 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)