[数据结构与算法]力扣 剑指 Offer II 114. 外星文字典

题目来源：https://leetcode.cn/problems/Jf1JuT/

大致题意：
给一个字符串数组，其中字符之间的大小关系已经被打乱了，但是目前数据是按照打乱后的关系升序排列，也就是说可以通过数组的升序关系获取字符串数组中出现字符之间的大小关系，求出这个大小关系，并按升序返回字符串

思路

通过相邻字符串可以获取一对字符之间的大小关系，这个关系就像一条有向边，比如字符串 “we” < “ew”，就可以知道 w < e，于是可以看作一条有向边 w -> e

按照这个方法遍历数组，就可以获得一个表示字符之间大小关系的有向图。

然后对这个有向图进行拓扑排序，即可获取所有出现字符的大小关系对应的字符串

具体实现拓扑排序可以通过深度优先搜索，也可以通过广度优先搜素，在构建图中如果出现环，那么给定的字符串数组无法找出有效的大小关系

DFS

使用深度优先搜索实现

1. 先根据升序排列的字符串数组获取有向图的所有边（获取过程中，若出现前一个字符串大于后一个，那么这个字符串数组无法找出有效大小关系，做标记）
2. 初始化一个字符状态数组，标记所有字符串中出现的字符目前在搜索中的状态

-1 表示未搜索
0 表示搜索中
1 表示搜索完毕

3. 遍历所有出现的字符，若对应字符未搜索过，则将其作为起点进行 dfs
4. dfs 搜索开始时，将当前节点字符对应状态修改为搜索中，然后搜索当前节点的所有出边对应节点。若对应节点状态为搜索中，表示出现环，标记并退出搜索；若对应状态为搜索完毕，跳过；若对应状态为未搜索，递归搜索该节点。当前节点搜索完毕后，更新节点字符对应状态，并将字符放入答案数组（dfs 完成的顺序和拓扑排序相反，所以在搜索完成时可以逆向放入字符）

代码：

Map<Character, List<Character>> edges;  // 存有向边，键为字符，值为字符出边对应的节点集合
    int[] states;   // 字符状态
    char[] ans;     // 答案数组
    int idx;        // 逆向存答案数组对应的索引
    boolean vaild;  // 标记是否可以找到有效的大小关系
    public String alienOrder_dfs(String[] words) {
        edges = new HashMap<>();
        states = new int[26];
        // 状态初始化
        Arrays.fill(states, -1);
        int n = words.length;
        // 获取所有出现的字符，并初始化有向边哈希表
        for (String word : words) {
            for (int j = 0; j < word.length(); j++) {
                edges.putIfAbsent(word.charAt(j), new ArrayList<>());
            }
        }
        // 标记初始化
        vaild = true;
        // 获取所有有向边
        for (int i = 1; i < n && vaild; i++) {
            addEdges(words[i - 1], words[i]);
        }
        // 答案数组索引初始化
        idx = edges.size() - 1;
        // 答案数组初始化
        ans = new char[idx + 1];
        // 以所有未搜索节点为 dfs 起点开始搜索
        for (Character c : edges.keySet()) {
            if (states[c - 'a'] < 0) {
                dfs(c);
            }
            // 如果标记当前字符串数组无效，直接返回答案
            if (!vaild) {
                return "";
            }
        }
        return new String(ans);
    }
    // 根据字符串大小关系获取有向边
    public void addEdges(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int t = 0;
        int len = Math.min(len1, len2);
        while (t < len) {
            char c1 = word1.charAt(t);
            char c2 = word2.charAt(t);
            // 字符不同，得到大小关系有向边
            if (c1 != c2) {
                edges.get(c1).add(c2);
                break;
            }
            t++;
        }
        // 出现了前一个字符串大于后一个字符串的情况，做标记
        // 如 "ab" 和 "a" 
        if (t == len && len1 > len2) {
            vaild = false;
        }
    }

    public void dfs(char c) {
        // 标记状态为搜索中
        states[c - 'a'] = 0;
        // 搜索所有出边节点
        for (Character ch : edges.get(c)) {
            int state = states[ch - 'a'];
            // 对应状态为搜索中，标记无效
            if (state == 0) {
                vaild = false;
                return;
            } else if (state < 0) { // 对应状态为未搜索，递归搜索
                dfs(ch);
                if (!vaild) {
                    return;
                }
            }
        }
        // 将搜索完毕字符加入答案数组
        ans[idx--] = c;
        // 更新状态
        states[c - 'a'] = 1;
    }

bfs

1. 获取所有有向边和所有字符的入度（获取时同样判断给定字符串数组是否有效）
2. 将所有入度为 0 的节点作为 bfs 搜索（bfs 搜索顺序与拓扑排序相同）起点
3. bfs 搜索时，遍历当前节点的有向边，将对应出边节点的入度 -1，若 -1 对应节点入度为 0，则将其加入 bfs 队列
4. 搜索完毕后，若搜索过的节点数量与所有出现字符数量相同，表示该有向图无环，返回答案；否则，该有向图有环，无效

代码：

	Map<Character, List<Character>> edges;  // 存有向边，键为字符，值为字符出边对应的节点集合
    boolean vaild;  // 标记是否可以找到有效的大小关系
	public String alienOrder_bfs(String[] words) {
        edges = new HashMap<>();
        int[] indegrees = new int[26];
        // 获取所有出现的字符，并初始化有向边哈希表
        for (String word : words) {
            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                edges.putIfAbsent(c, new ArrayList<>());
            }
        }
        // 答案数组
        char[] ans = new char[edges.size()];
        // 标记初始化
        vaild = true;
        // 获取所有有向边和节点对应入度
        for (int i = 1; i < words.length && vaild; i++) {
            addEdges_bfs(words[i - 1], words[i], indegrees);
        }
        // 若标记无效，直接返回答案
        if (!vaild) {
            return "";
        }
        // bfs 队列
        Queue<Character> queue = new ArrayDeque<>();
        // 将所有入度为 0 节点作为起点
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            if (indegrees[i] == 0 && edges.containsKey(c)) {
                queue.offer(c);
            }
        }
        // 索引初始化
        int idx = 0;
        // bfs 搜索
        while (!queue.isEmpty()) {
            char cur = queue.poll();
            // 搜索的顺序即为答案
            ans[idx++] = cur;
            // 遍历所有出边
            for (Character ch : edges.get(cur)) {
                // 将对应出边节点入度 --
                indegrees[ch - 'a']--;
                // 若入度为 0，加入队列
                if (indegrees[ch - 'a'] == 0) {
                    queue.offer(ch);
                }
            }
        }
        // 根据搜索过的节点数量判断是否出现环
        return idx == edges.size() ? new String(ans) : "";
    }

    public void addEdges_bfs(String word1, String word2, int[] indegrees) {
        int len1 = word1.length();
        int len2 = word2.length();
        int t = 0;
        int len = Math.min(len1, len2);
        while (t < len) {
            char c1 = word1.charAt(t);
            char c2 = word2.charAt(t);
            // 字符不同，获取大小关系有向边
            if (c1 != c2) {
                edges.get(c1).add(c2);
                // 更新对应字符入度
                indegrees[c2 - 'a']++;
                break;
            }
            t++;
        }
        if (t == len && len1 > len2) {
            vaild = false;
        }
    }