Skip to content

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<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;
  }
};

 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<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;
  }
}

 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)