Java编程题 - 外星文字典详解（拓扑排序+深度优先搜索）

• 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
• 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

• 字母之间的顺序关系存在由至少 22 个字母组成的环，例如 words=["a","b","a"]
• 相邻两个单词满足后面的单词是前面的单词的前缀，且后面的单词的长度小于前面的单词的长度，例如 words=["ab",“a"]

public class AlienOrder {
  // 通过输入的字典，返回字符顺序（拓扑排序 + 广度优先搜索）
  public static String getOrder(String[] words) {
    // 存储图（当前节点字符对应下一个节点字符，下一个节点可能有多个）
    Map<Character,List<Character>> graph = new HashMap<>();
    // 存储每个字符节点的入度
    Map<Character, Integer> indegrees = new HashMap<Character, Integer>();

    // 初始化图（将所有的字符作为key存入graph）
    for(String word:words){
      for(int j = 0; j < word.length(); j++){
        graph.putIfAbsent(word.charAt(j),new ArrayList<>());
      }
    }

    // 两两单词比较构建图和入度数据
    for(int i = 0; i < words.length-1; i++){
      String w1 = words[i];
      String w2 = words[i+1];
      int minLength = Math.min(w1.length(),w2.length());
      int j = 0;
      while (j < minLength) {
        // 逐个比较字符直到不相同的时候
        if(w1.charAt(j) != w2.charAt(j)){
          char c1 = w1.charAt(j);
          char c2 = w2.charAt(j);
          // 增加边联系（c1->c2）
          graph.get(c1).add(c2);
          // c2入度+1
          indegrees.put(c2, indegrees.getOrDefault(c2, 0) + 1);
          break;
        }
        j++;
      }
      //存在不合法的情况 前一个字符串长度大于当前字符串长度 但前minLength均相等
      if(j == minLength && w1.length()>w2.length()) return "";
    }

    // 存储顺序字符串
    StringBuilder sb = new StringBuilder();
    // 初始时将所有入度为 0 的节点入队列
    Queue<Character> queue = new LinkedList<>();
    for (Character ch : graph.keySet()) {
      if (!indegrees.containsKey(ch)) {
        queue.offer(ch);
      }
    }

    // 队列中是否存在入度为0的点
    while (!queue.isEmpty()){
      // 有的话则输出
      Character ch = queue.poll();
      sb.append(ch);
      // 判断当前输出的节点下一个相联系的节点
      if(graph.containsKey(ch)) {
        for(Character next: graph.get(ch)){
          //下一个相联系的节点入度-1
          indegrees.put(next, indegrees.get(next) - 1);
          //如果-1后如果变为0则加入队列
          if(indegrees.get(next)==0){
            queue.offer(next);
          }
        }
      }
    }

    // 返回最终结果（判断是否所有的点都加入了结果集，如果不是则存在环，返回空字符串表示不存在合法字母顺序）
    return sb.length() < graph.size()? "" : sb.toString();
  }

  public static void main(String[] args) {
    String[] ws1 = {"z","x","a"};
    System.out.println("输入：" + Arrays.toString(ws1));
    System.out.println("输出：" + getOrder(ws1));

    String[] ws2 = {"cd","bnc","ca"};
    System.out.println("输入：" + Arrays.toString(ws2));
    System.out.println("输出：" + getOrder(ws2));

    String[] ws3 = {"wrt","wrf","er","ett", "ec"};
    System.out.println("输入：" + Arrays.toString(ws3));
    System.out.println("输出：" + getOrder(ws3));

    String[] ws4 = {"we","wr","wt","wf","er","eq","cc","ct"};
    System.out.println("输入：" + Arrays.toString(ws4));
    System.out.println("输出：" + getOrder(ws4));
  }
}