269. 火星字典

题设¶

现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。

假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个不为空的单词列表。因为是从词典中获得的，所以该单词列表内的单词已经按这门新语言的字母顺序进行了排序。

您需要根据这个输入的列表，还原出此语言中已知的字母顺序。

输入:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
输出: "wertf"

解法一：拓扑排序¶

第一步：根据输入构建一个有向图
- 逐位比较两个相互挨着的字符串
- 当两个字符串某个相同位置出现不同，即可得出它们顺序，无需继续比较剩余字符。
第二步：对该图进行拓扑排序

var alienOrder = function(words) {
  if (words === null || words.length === 0) {
    return null;
  }
  if (words.length === 1) {
    return words[0];
  }

  // 第一步：创建有向图，已邻接表的方式表示
  const adjList = {};

  for(let i = 0; i < words.length - 1; i++) {
    let w1 = words[i];
    let w2 = words[i + 1];

    // 表示一旦出现不同字母，则连接这两个顶点，之后的字符不必处理
    let found = false;

    for(let j = 0; j < Math.max(w1.length, w2.length); j++) {
      let c1 = w1[j], c2 = w2[j];

      // 为每个出现的字符创建顶点
      if (c1) {
        adjList[c1] = adjList[c1] || [];
      }
      if (c2) {
        adjList[c2] = adjList[c2] || [];
      }

      if(c1 && c2 && c1 !== c2 && !found) {
        adjList[c1].push(c2);
        found = true;
      }
    }
  }

  // 第二步：拓扑排序
  let visited = {}; // 记录已经访问过的顶点
  let loop = {}; // 防止有向图中出现环的情况
  let stack = []; // 记录拓扑排序顶点顺序：从某顶点出发，直到访问完其他顶点，才入栈

  for(let key in adjList) {
    if (!visited[key]) {
      if (!topologicalSort(adjList, key, visited, loop, stack)) {
        return '';
      };
    }
  }

  return stack.reverse().join('');
};

// 深度优先方式实现拓扑排序
function topologicalSort(adjList, v, visited, loop, stack) {
  visited[v] = true;
  loop[v] = true;

  if (adjList[v]) {
    for(let i = 0; i < adjList[v].length; i++) {
      let u = adjList[v][i];

      // 如果本轮访问中，u 已经被访问过，说明有环出现，则返回 false
      if (loop[u]) {
        return false;
      }

      // 如果 u 没被访问过，则开始递归
      if(!visited[u]) {
        if (!topologicalSort(adjList, u, visited, loop, stack)) {
          return false; // 如果递归访问时，出现环，则返回 false
        }
      }
    }
  }

  // 从 v 出发，访问完所有顶点，则此轮访问没有环，置为 false
  loop[v] = false;

  // 等所有依赖 v 的节点遍历完，v 才入栈
  stack.push(v);
  return true; // 返回 true，表示没有发现环
}