Verbal Arithmetic Puzzle

Given an equation, represented by words on left side and the result on right side.

You need to check if the equation is solvable under the following rules:

Each character is decoded as one digit (0 - 9).
Every pair of different characters they must map to different digits.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on left side (words) will equal to the number on 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 = ["THIS","IS","TOO"], result = "FUNNY"
Output: true

Example 4:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false

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.

Solution:

class Solution {
    Set<Character> chars = new HashSet();
    Set<Character> firsts = new HashSet();
    List<Character> charList;
    String[] w;
    String res;
    
    public boolean isSolvable(String[] words, String result) {
        w = words;
        res = result;
        for (String s : words) {
            for (int i = 0; i < s.length(); i ++) {
                char c = s.charAt(i);
                if (i == 0) {
                    firsts.add(c);
                }
                chars.add(c);
            }
        }
        firsts.add(result.charAt(0));
        for (char c : result.toCharArray()) {
            chars.add(c);
        }
        charList = new ArrayList(chars);
        Integer[] arr = new Integer[charList.size()];
        return bt(arr, new HashSet(), 0);
    }
    
    private boolean bt(Integer[] arr, Set<Integer> used, int i) {
        if (i == arr.length) {
            if (isValid(arr, charList, w, res)) {
                System.out.println(Arrays.toString(arr));
                System.out.println(charList);

                return true;
            }
            return false;
        }
        char c = charList.get(i);
        for (int val = 0; val < 10; val ++) {
            if (val == 0 && firsts.contains(c)) continue;
            if (used.contains(val)) continue;
            arr[i] = val;
            used.add(val);
            if (bt(arr, used, i + 1)) return true;
            used.remove(val);
            arr[i] = null;
        }
        return false;
    }
    
    private boolean isValid(Integer[] arr, List<Character> chars, String[] words, String result) {
        Map<Character, Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i ++) {
            map.put(chars.get(i), arr[i]);
        }
        int sum = 0;
        for (String s : words) {
            int curr = 0;
            for (int i = 0; i < s.length(); i ++) {
                curr = curr * 10 + map.get(s.charAt(i));
            }
            sum += curr;
        }
        int target = 0;
        for (int i = 0; i < result.length(); i ++) {
            target = target * 10 + map.get(result.charAt(i));
        }
        return sum == target;
    }
}

class Solution {
    private static final int[] POW_10 = new int[]{1, 10, 100, 1000, 10000, 100000, 1000000};
    public boolean isSolvable(String[] words, String result) {
        Set<Character> charSet = new HashSet<>();
        int[] charCount = new int[91];
        boolean[] nonLeadingZero = new boolean[91]; // ASCII of `A..Z` chars are in range `65..90`
        for (String word : words) {
            char[] cs = word.toCharArray();
            for (int i = 0; i < cs.length; i++) {
                if (i == 0 && cs.length > 1) nonLeadingZero[cs[i]] = true;
                charSet.add(cs[i]);
                charCount[cs[i]] += POW_10[cs.length - i - 1]; // charCount is calculated by units
            }
        }
        char[] cs = result.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (i == 0 && cs.length > 1) nonLeadingZero[cs[i]] = true;
            charSet.add(cs[i]);
            charCount[cs[i]] -= POW_10[cs.length - i - 1]; // charCount is calculated by units
        }
        boolean[] used = new boolean[10];
        char[] charList = new char[charSet.size()];
        int i = 0;
        for (char c : charSet) charList[i++] = c;
        return backtracking(used, charList, nonLeadingZero, 0, 0, charCount);
    }

    private boolean backtracking(boolean[] used, char[] charList, boolean[] nonLeadingZero, int step, int diff, int[] charCount) {
        if (step == charList.length) return diff == 0; // difference between sum of words and result equal to 0
        for (int d = 0; d <= 9; d++) { // each character is decoded as one digit (0 - 9).
            char c = charList[step];
            if (!used[d] // each different characters must map to different digits
                    && (d > 0 || !nonLeadingZero[c])) {  // decoded as one number without leading zeros.
                used[d] = true;
                if (backtracking(used, charList, nonLeadingZero, step + 1, diff + charCount[c] * d, charCount)) return true;
                used[d] = false;
            }
        }
        return false;
    }
}