1
class Solution {
2
  public static boolean isSolvable(String[] words, String result) {
3
    // reverse all strings to facilitate add calculation.
4
    for (int i = 0; i < words.length; i++) {
5
      words[i] = new StringBuilder(words[i]).reverse().toString();
6
    }
7
    result = new StringBuilder(result).reverse().toString();
8
    if (!checkLength(words, result)) {
9
      return false;
10
    }
11
    boolean[] visited = new boolean[10]; // digit 0, 1, ..., 9
12
    int[] chToDigit = new int[26];
13
    Arrays.fill(chToDigit, -1);
14
    return dfs(0, 0, 0, visited, chToDigit, words, result);
15
  }
16

17
  /** Elminate the case where result is too long word1: AAA word2: BBB result: XXXXXXXXX */
18
  private static boolean checkLength(String[] words, String result) {
19
    int maxLen = 0;
20
    for (String word : words) {
21
      maxLen = Math.max(maxLen, word.length());
22
    }
23
    return result.length() == maxLen || result.length() == maxLen + 1;
24
  }
25

26
  /*
27
  Put all words like this:
28
  w1:     ABC
29
  w2:     EF
30
  w3:     GHIJ
31
  result: KLMNO
32
  i, is the row
33
  j,  is the column
34
  carrier, the one contributed from previous calculation
35
  chToDigit, 26 int array, which records choosen digit for 'A', 'B', 'C', ... If not choosen any, default is -1
36
   */
37
  private static boolean dfs(
38
      int i,
39
      int j,
40
      int carrier,
41
      boolean[] visited,
42
      int[] chToDigit,
43
      String[] words,
44
      String result) {
45
    if (i == words.length) {
46
      char ch = result.charAt(j);
47
      // (i, i) at bottom right corner. final check
48
      if (j == result.length() - 1) {
49
        // 1. check if carrier is equal or greater than 10. If so, false.
50
        if (carrier >= 10) {
51
          return false;
52
        }
53
        // 2. check if result.length() > 1 && result.lastCh is zero. If so the false.
54
        if (j > 0 && j == result.length() - 1 && chToDigit[ch - 'A'] == 0) {
55
          return false;
56
        }
57
        // not selected, can select any. True.
58
        if (chToDigit[ch - 'A'] == -1) {
59
          System.out.println(Arrays.toString(chToDigit));
60
          return true;
61
        } else { // if selected, check if it matches with carrier. Also, carrier can't be 0. result
62
          // = '00' is invalid
63
          return chToDigit[ch - 'A'] == carrier;
64
        }
65
      } else { // reached normal result line.
66
        // 1. if not selected. Use current carrier's unit digit
67
        if (chToDigit[ch - 'A'] == -1) {
68
          int selectedDigit = carrier % 10;
69
          // For example carrier = 13. selectedDigit = 3. ch = 'H'. Should set 3 to 'H'.
70
          // But 3 is already taken by 'B' previously. So wrong.
71
          if (visited[selectedDigit]) {
72
            return false;
73
          }
74
          visited[selectedDigit] = true;
75
          chToDigit[ch - 'A'] = selectedDigit;
76
          if (dfs(0, j + 1, carrier / 10, visited, chToDigit, words, result)) {
77
            return true;
78
          }
79
          chToDigit[ch - 'A'] = -1;
80
          visited[selectedDigit] = false;
81
        } else { // 2. selected
82
          // just need to check if ch.digit equals to unit digit.
83
          if (chToDigit[ch - 'A'] != carrier % 10) {
84
            return false;
85
          }
86
          boolean ans = dfs(0, j + 1, carrier / 10, visited, chToDigit, words, result);
87
          return ans;
88
        }
89
      } //
90
    } else { // normal word
91
      String word = words[i];
92
      // 1. check if j is equal or greater than word.len. If so pass to next word.
93
      if (j >= word.length()) {
94
        boolean ans = dfs(i + 1, j, carrier, visited, chToDigit, words, result);
95
        return ans;
96
      }
97
      // 2. check if it's last ch, word.len is greater than 1, and is '0'. If so false;
98
      if (j == word.length() - 1 && word.length() > 1 && chToDigit[word.charAt(j) - 'A'] == 0) {
99
        return false;
100
      }
101
      char ch = word.charAt(j);
102
      // 3. check if word.ch is selected. Just add current digit and move to next word.
103
      if (chToDigit[ch - 'A'] != -1) {
104
        int newSum = carrier + chToDigit[ch - 'A'];
105
        boolean ans = dfs(i + 1, j, newSum, visited, chToDigit, words, result);
106
        return ans;
107
      } else {
108
        for (int k = 0; k < visited.length; k++) {
109
          if (visited[k]) {
110
            continue;
111
          }
112
          visited[k] = true;
113
          chToDigit[ch - 'A'] = k;
114
          int newSum = k + carrier;
115
          boolean ans = dfs(i + 1, j, newSum, visited, chToDigit, words, result);
116
          if (ans) {
117
            return true;
118
          }
119
          visited[k] = false;
120
          chToDigit[ch - 'A'] = -1;
121
        }
122
      }
123
    }
124
    return false;
125
  }
126
}