返回 导航

其他

hangge.com

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

作者：hangge | 2022-12-12 08:50

1，题目描述

（1）现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
（2）给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经按这门新语言的字母顺序进行了排序 。
（3）请你根据该词典还原出此语言中已知的字母顺序，并按字母递增顺序排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中任意一种顺序即可。
（4）字符串 s 字典顺序小于 字符串 t 有两种情况：
  • 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
  • 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

2，解题思路

（1）根据描述可以得知外星文字母排序并不是正常的 abcd....，而是需要根据我们给定的字符串列表来推算出字母顺序，比如：
  • 输入：["z","x"] 输出："zx"
  • 输入：["wrt","wrf","er","ett","rftt"] 输出："wertf"

（2）但有以下两种情况不存在合法字母顺序：
  • 字母之间的顺序关系存在由至少 22 个字母组成的环，例如 words=["a","b","a"]
  • 相邻两个单词满足后面的单词是前面的单词的前缀，且后面的单词的长度小于前面的单词的长度，例如 words=["ab",“a"]

（3）这道题是拓扑排序问题。将外星文字典中的每个字母看成一个节点，将字母之间的顺序关系看成有向边。对于外星文字典中的两个相邻单词，同时从左到右遍历，当遇到第一个不相同的字母时，该位置的两个字母之间即存在顺序关系。比如通过字符串列表 ["we","wr","wt","wf","er","eq","cc","ct"] 可以构建出如下拓扑图：

（4）拓扑排序可以使用深度优先搜索或广度优先搜索实现，这里我们使用广度优先搜索。具体做法是，使用队列存储可以加入拓扑排序的节点，初始时将所有入度为 0 的节点入队列。每次将一个节点出队列并加入拓扑排序中，然后将该节点的所有相邻节点的入度都减 1，如果一个相邻节点的入度变成 0，则将该相邻节点入队列。重复上述操作，直到队列为空时，广度优先搜索结束。
提示：广度优先搜索结束时，判断拓扑排序的长度是否等于字典中的字母个数，即可判断有向图中是否有环。
  • 如果拓扑排序的长度等于字典中的字母个数，则拓扑排序包含字典中的所有字母，返回拓扑排序；
  • 如果拓扑排序的长度小于字典中的字母个数，则有向图中有环，不存在拓扑排序。

3，解题代码

（1）代码具体的实现逻辑如下：
  • 记录所有出现字母的入度和图的映射关系
  • 不合法情况（前面的长后面的短，短的部分两者相同，abc 和 ab）这种情况直接返回
  • 入度为 0 的点入队
  • 逐个出队，减少到达点的入度，入度为 0 的入队
  • 最终需要确定是否所有已有字母都完成了排序，如果没有，则说明字典构建失败，需要返回空
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));
  }
}

（2）运行结果如下：
评论

全部评论（0）

回到顶部