火星词典

/*
思路：
1. 使用流处理构建图和入度数组。
2. 使用流进行拓扑排序。
*/
import java.util.*;
import java.util.stream.*;

public class AlienDictionaryStream {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        Arrays.stream(words).forEach(word -> {
            word.chars().forEach(c -> {
                graph.putIfAbsent((char) c, new HashSet<>());
                inDegree.putIfAbsent((char) c, 0);
            });
        });
        IntStream.range(0, words.length - 1).forEach(i -> {
            String word1 = words[i];
            String word2 = words[i + 1];
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return;
            }
            IntStream.range(0, Math.min(word1.length(), word2.length())).filter(j -> word1.charAt(j) != word2.charAt(j)).findFirst().ifPresent(j -> {
                char parent = word1.charAt(j);
                char child = word2.charAt(j);
                if (graph.get(parent).add(child)) {
                    inDegree.put(child, inDegree.get(child) + 1);
                }
            });
        });
        Queue<Character> queue = inDegree.keySet().stream().filter(c -> inDegree.get(c) == 0).collect(Collectors.toCollection(LinkedList::new));
        StringBuilder order = new StringBuilder();
        while (!queue.isEmpty()) {
            char current = queue.poll();
            order.append(current);
            graph.get(current).forEach(neighbor -> {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            });
        }
        return order.length() == inDegree.size() ? order.toString() : "";
    }
}