简介：private Map Character, Set Character constructGraph(String[] words) { Map Character, Set Character graph = new HashMap (); // create nodes for (int i = 0; i words.length; i++) { for (int j = 0; j words[i].length(); j++) { char c = words[i]……
private Map Character, Set Character constructGraph(String[] words) {
Map Character, Set Character graph = new HashMap ();
// create nodes
for (int i = 0; i words.length; i++) {
for (int j = 0; j words[i].length(); j++) {
char c = words[i].charAt(j);
if (!graph.containsKey(c)) {
graph.put(c, new HashSet Character
// create edges
for (int i = 0; i words.length - 1; i++) {
int index = 0;
while (index words[i].length() index words[i + 1].length()) {
if (words[i].charAt(index) != words[i + 1].charAt(index)) {
graph.get(words[i].charAt(index)).add(words[i + 1].charAt(index));
break;
index++;
if (index == Math.min(words[i].length(), words[i + 1].length())) {
if (words[i].length() words[i + 1].length()) {
return null;
return graph;
private Map Character, Integer getIndegree(Map Character, Set Character graph) {
Map Character, Integer indegree = new HashMap ();
for (Character u : graph.keySet()) {
indegree.put(u, 0);
for (Character u : graph.keySet()) {
for (Character v : graph.get(u)) {
indegree.put(v, indegree.get(v) + 1);
return indegree;
private String topologicalSorting(Map Character, Set Character graph) {
// as we should return the topo order with lexicographical order
// we should use PriorityQueue instead of a FIFO Queue
Map Character, Integer indegree = getIndegree(graph);
Queue Character queue = new PriorityQueue ();
for (Character u : indegree.keySet()) {
if (indegree.get(u) == 0) {
queue.offer(u);
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
Character head = queue.poll();
sb.append(head);
for (Character neighbor : graph.get(head)) {
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
queue.offer(neighbor);
if (sb.length() != indegree.size()) {
return "";
return sb.toString();
}
更多题解参考：九章官网solution
本文转自网络，原文链接：https://developer.aliyun.com/article/784415
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！
