[LeetCode] BFS 269. Alien Dictionary

문제

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

 

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of only lowercase English letters.

---

코드

var alienOrder = function (words) {
  const queue = [];
  const graph = new Map();
  const indegree = new Map();
  const result = [];

  // 글자들을 문자들로 쪼개서
  // 글자들에 매핑할 단어를 넣을 array를 추가
  // 그리고 각 문자에 들어올 진입차수(indegree)를 넣을 숫자 객체를 담음
  for (let word of words) {
    for (let char of word) {
      if (!graph.has(char)) {
        graph.set(char, []);
      }

      if (!indegree.has(char)) {
        indegree.set(char, 0);
      }
    }
  }

  // 앞 문자열과 뒷 문자열을 비교해서
  // 서로 다른 문자열이라면
  // word1에서 word2로 오는 것을 진입차수라고 생각하고
  // word2에 해당하는 indegress에 1을 추가
  for (let i = 1; i < words.length; i++) {
    let word1 = words[i - 1];
    let word2 = words[i];
    let length = Math.min(word1.length, word2.length);

    // If wrong order
    if (word2.length < word1.length && word1.startsWith(word2)) {
      return "";
    }

    for (let j = 0; j < length; j++) {
      if (word1[j] !== word2[j]) {
        graph.get(word1[j]).push(word2[j]);

        indegree.set(word2[j], indegree.get(word2[j]) + 1);
        break;
      }
    }
  }

  // indegree에서 0인것을 미리 queue에 넣고 BFS 정렬시작
  for (let c of indegree) {
    if (c[1] === 0) {
      queue.push(c[0]);
    }
  }

  // BFS
  while (queue.length) {
    let vertex = queue.shift();
    for (let char of graph.get(vertex)) {
      let val = indegree.get(char) - 1;
      indegree.set(char, val);

      // val === 0이 됐다는건 => 다음 정렬 차례라는 것을 뜻함
      if (val === 0) queue.push(char);
    }
    result.push(vertex);
  }

  return result.length === indegree.size ? result.join("") : "";
};