LeetCode 269. 火星词典

Categories:

题目描述
思路分析
1. 解法一：拓扑排序（推荐）
相似题目

题目描述

✅ 269. 火星词典

思路分析

解法一：拓扑排序（推荐）

核心思路：

相邻单词对比，找到第一个不同字符，建立有向边。

若出现前缀冲突（长词在前且是短词前缀），直接返回空串。

对图进行拓扑排序，若结果长度不足说明存在环。

复杂度分析：

时间复杂度：O(V + E)，其中 V 表示字母种类数，E 表示有向边数。

空间复杂度：O(V + E)，用于图结构与入度统计。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();

        // 初始化所有字符
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                graph.putIfAbsent(ch, new HashSet<>());
                indegree.putIfAbsent(ch, 0);
            }
        }

        // 构建有向边
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            int len = Math.min(w1.length(), w2.length());
            int j = 0;
            while (j < len && w1.charAt(j) == w2.charAt(j)) {
                j++;
            }
            if (j == len && w1.length() > w2.length()) {
                return "";
            }
            if (j < len) {
                char from = w1.charAt(j);
                char to = w2.charAt(j);
                if (graph.get(from).add(to)) {
                    indegree.put(to, indegree.get(to) + 1);
                }
            }
        }

        Queue<Character> queue = new ArrayDeque<>();
        for (char ch : indegree.keySet()) {
            if (indegree.get(ch) == 0) {
                queue.offer(ch);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char cur = queue.poll();
            sb.append(cur);
            for (char next : graph.get(cur)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }

        return sb.length() == indegree.size() ? sb.toString() : "";
    }
}

func alienOrder(words []string) string {
	graph := make(map[byte]map[byte]struct{})
	indegree := make(map[byte]int)

	// 初始化所有字符
	for _, w := range words {
		for i := 0; i < len(w); i++ {
			ch := w[i]
			if _, ok := graph[ch]; !ok {
				graph[ch] = make(map[byte]struct{})
			}
			if _, ok := indegree[ch]; !ok {
				indegree[ch] = 0
			}
		}
	}

	// 构建有向边
	for i := 0; i < len(words)-1; i++ {
		w1 := words[i]
		w2 := words[i+1]
		minLen := len(w1)
		if len(w2) < minLen {
			minLen = len(w2)
		}
		j := 0
		for j < minLen && w1[j] == w2[j] {
			j++
		}
		if j == minLen && len(w1) > len(w2) {
			return ""
		}
		if j < minLen {
			from := w1[j]
			to := w2[j]
			if _, ok := graph[from][to]; !ok {
				graph[from][to] = struct{}{}
				indegree[to]++
			}
		}
	}

	queue := make([]byte, 0)
	for ch, deg := range indegree {
		if deg == 0 {
			queue = append(queue, ch)
		}
	}

	order := make([]byte, 0, len(indegree))
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		order = append(order, cur)
		for next := range graph[cur] {
			indegree[next]--
			if indegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}

	if len(order) != len(indegree) {
		return ""
	}
	return string(order)
}

相似题目

题目	难度	考察点
207. 课程表	中等	拓扑排序
210. 课程表 II	中等	拓扑排序
444. 序列重建	中等	拓扑排序
1136. 并行课程	中等	拓扑排序
1203. 项目管理	困难	拓扑排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79254259