# 1307. Verbal Arithmetic Puzzle
###### tags: `Leetcode` `Hard` `Backtracking`
Link: https://github.com/wisdompeak/LeetCode/tree/master/DFS/1307.Verbal-Arithmetic-Puzzle
## 思路
一位一位先后往前处理
参考[思路](https://github.com/wisdompeak/LeetCode/tree/master/DFS/1307.Verbal-Arithmetic-Puzzle)
当同一位数字处理完之后，我们需要检查他们的sum是否与result对应位的数字一致
我们需要考虑剪枝的情况:
1. result对应位的字母已经匹配过数字了 和sum%10不一样
2. result对应位的字母没有匹配数字 但是sum%10已经匹配给别人了

同时我们要检查不能让0成为任何一个字符串的首字母对应的数字
## Code

class Solution {
    int[] map = new int[26];
    boolean[] used = new boolean[10];
    public boolean isSolvable(String[] words, String result) {
        Arrays.fill(map, -1);
        for(String word:words) if(word.length()>result.length()) return false;
        return dfs(0, 0, 0, words, result);
    }
    private boolean dfs(int i, int j, int sum, String[] words, String result){
        //j 表示已经处理到result的倒数第几位(因为是加法所以每个字符串都要从前往后看)
        //i 表示已经处理到哪个word了
        if(j==result.length()){
            //已经处理完result的最后一位
            if(sum!=0) return false;
            if(result.length()>1 && map[result.charAt(0)-'A']==0) return false;
            return true;
        }
        int resSZ = result.length();
        if(i==words.length){
            //对于第j位来说我们已经遍历完了所有的word 所以我们要看现在sum能不能和result的对应位匹配上
            if(map[result.charAt(resSZ-j-1)-'A']!=-1){
                // 剪枝的第一种情况
                if(map[result.charAt(resSZ-j-1)-'A']==sum%10){
                    return dfs(0, j+1, sum/10, words, result);
                }
                return false;
            }
            else{
                // 剪枝的第二种情况
                if(used[sum%10]) return false;
                map[result.charAt(resSZ-j-1)-'A']=sum%10;
                used[sum%10] = true;
                if(dfs(0, j+1, sum/10, words, result)) return true;
                map[result.charAt(resSZ-j-1)-'A']=-1;
                used[sum%10] = false;
                return false;
            }
        }
        
        //我们要看words[i]的倒数第j位 但words[i]根本没有倒数第j位
        if(j>=words[i].length()) return dfs(i+1, j, sum, words, result);
        
        //尝试给words[i]的倒数第j位放一个数字
        int size = words[i].length();
        char ch = words[i].charAt(size-j-1);
        if(map[ch-'A']!=-1){
            if(size>1 && size-j-1==0 && map[ch-'A']==0) return false;
            return dfs(i+1, j, sum+map[ch-'A'], words, result);
        }
        else{
             for (int d=0; d<=9; d++){
                if (used[d]) 
                    continue;
                if (d==0 && words[i].length()>1 && j==words[i].length()-1)
                    continue;
                map[ch-'A'] = d;
                used[d] = true;
                if (dfs(i+1, j, sum+d, words, result))
                    return true;                
                map[ch-'A'] = -1;
                used[d] = false;
            }
            return false;
        }
    }
}