阿里9.8笔试 第二题回溯解法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        while (n != 0){
            Set<String> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                set.add(reader.readLine());
            }
            String str = reader.readLine();
            String[] after = str.substring(0,str.length()-1).split(" ");
            Map<Character,Character> key = new HashMap<>();
            List<String> res = new ArrayList<>();
            solve(after,0,set,key,res);
            if (res.size() == 1){
                System.out.println(res.get(0) + ".");
            }else {
                System.out.println("-.");
            }
            n = Integer.parseInt(reader.readLine());
        }

    }

    /**
     * 回溯解法
     * @param after 加密后的字符串数组
     * @param k 本次解到after[k]
     * @param set 保存为解密的原字符串
     * @param key 保存已经解得的字符对
     * @param res 最后结果
     */
    public static void solve(String[] after, int k, Set<String> set, Map<Character,Character> key, List<String> res){
        //终止条件
        if(set.size() == 0 || k >= after.length){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < after.length; i++) {
                for (int j = 0; j < after[i].length(); j++) {
                    if (key.containsKey(after[i].charAt(j))){
                        sb.append(key.get(after[i].charAt(j)));
                    }else {
                        return;
                    }
                }
                sb.append(" ");
            }
            res.add(sb.toString());
            return;
        }
        //如果after所有字符都被解码，直接下一轮
        boolean flag = true;
        for (int i = 0; i < after[k].length(); i++) {
            if (!key.containsKey(after[k].charAt(i))){
                flag = false;
            }
        }
        if (flag){
            solve(after,k+1,set,key,res);
        }else {
            for(String temp : set){
                if (temp.length() == after[k].length()){
                    Map<Character,Character> key2 = new HashMap<>();
                    Set<String> set2 = new HashSet<>();
                    key2.putAll(key);
                    set2.addAll(set);
                    for (int i = 0; i < after[k].length(); i++) {
                        char c = after[k].charAt(i);
                        if (!key2.containsKey(c)){
                            key2.put(c,temp.charAt(i));
                            key2.put(temp.charAt(i),c);
                        }else {
                            if (!key2.get(c).equals(temp.charAt(i))){
                                return;
                            }
                        }
                    }
                    set2.remove(temp);
                    solve(after, k+1, set2, key2,res);
                }
            }
        }
    }
}

/*原测试用例
4
CAT
A
DOG
AND
Z YZT ZVX Z XUW.
2
AB
AC
BA.
3
CC
DD
EE
FF.
*/