Alien Dictionary Hard 0 attempts

Alien Dictionary

Hard GraphBFSDFS Other

You're given a list of words that have already been sorted according to the rules of an unknown alien alphabet. Using the order in which these words appear, work out the relative ordering of the letters themselves, and return that ordering as a single string containing each observed letter exactly once. Return an empty string if the ordering is impossible, including cycles and a longer word appearing before its own prefix. If several orders work, return any valid one.

Input Format
Implement alienDictionary(words). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

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

Example 3

Input
words = ["abc","ab"]
Output
""
Constraints
  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters
Test Cases (4)
Case 1
Args: [["wrt","wrf","er","ett","rftt"]] Expected: "wertf"
Case 2
Args: [["z","x"]] Expected: "zx"
Case 3
Args: [["abc","ab"]] Expected: ""
Case 4
Args: [["z","x","z"]] Expected: ""
Topics
GraphBFSDFS

Topological Sort

Build a directed graph from adjacent word comparisons, then perform topological sort.

javascript
function alienDictionary(words) {
  const graph = new Map(), inDeg = new Map();
  for (const w of words) for (const c of w) { graph.set(c, new Set()); inDeg.set(c, 0); }
  for (let i = 0; i < words.length - 1; i++) {
    const [a, b] = [words[i], words[i+1]];
    const minLen = Math.min(a.length, b.length);
    if (a.length > b.length && a.slice(0, minLen) === b.slice(0, minLen)) return "";
    for (let j = 0; j < minLen; j++) {
      if (a[j] !== b[j]) {
        if (!graph.get(a[j]).has(b[j])) { graph.get(a[j]).add(b[j]); inDeg.set(b[j], inDeg.get(b[j])+1); }
        break;
      }
    }
  }
  const q = [...inDeg.keys()].filter(c => inDeg.get(c) === 0), res = [];
  let head = 0;
  while (head < q.length) {
    const c = q[head++]; res.push(c);
    for (const n of graph.get(c)) { inDeg.set(n, inDeg.get(n)-1); if (inDeg.get(n)===0) q.push(n); }
  }
  return res.length === inDeg.size ? res.join('') : "";
}

Time: O(C) where C = total chars | Space: O(U + min(U², N)) where U = unique chars

Saved in this browser only. Private to you.

JavaScript