火星词典

/*
题目思路:
1. 构建字符的入度表和邻接表。
2. 使用流式API对单词列表进行处理, 构建图并更新入度。
3. 使用流式API进行拓扑排序, 如果排序结果字符数与所有唯一字符数一致, 返回排序结果, 否则返回""。
*/
 
import java.util.*;
import java.util.stream.*;
 
public class AlienDictionaryStream {
    public String alienOrder(String[] words) {
        Map<Character, Long> inDegree = words.stream()
            .flatMapToInt(String::chars)
            .mapToObj(c -> (char) c)
            .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
 
        Map<Character, List<Character>> adjList = words.stream()
            .flatMapToInt(String::chars)
            .mapToObj(c -> (char) c)
            .distinct()
            .collect(Collectors.toMap(c -> c, c -> new ArrayList<>()));
 
        IntStream.range(0, words.length - 1).forEach(i -> {
            String first = words[i];
            String second = words[i + 1];
            if (first.length() > second.length() && first.startsWith(second)) {
                throw new IllegalArgumentException();
            }
            IntStream.range(0, Math.min(first.length(), second.length())).filter(j -> first.charAt(j) != second.charAt(j)).findFirst().ifPresent(j -> {
                adjList.get(first.charAt(j)).add(second.charAt(j));
                inDegree.put(second.charAt(j), inDegree.get(second.charAt(j)) + 1);
            });
        });
 
        Queue<Character> queue = inDegree.entrySet().stream()
            .filter(entry -> entry.getValue() == 0)
            .map(Map.Entry::getKey)
            .collect(Collectors.toCollection(LinkedList::new));
 
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char current = queue.poll();
            sb.append(current);
            adjList.get(current).forEach(neighbor -> {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            });
        }
 
        return sb.length() < inDegree.size() ? "" : sb.toString();
    }
}