269. Alien dictionary

269_solution1_kahn.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

char *foreignDictionary(char **words, int wordsSize) {
  bool seen[26] = {0};
  bool edge[26][26] = {{0}};
  int indeg[26] = {0};
  int total = 0;

  for (int i = 0; i < wordsSize; i++)
    for (char *p = words[i]; *p; p++)
      if (!seen[*p - 'a']) {
        seen[*p - 'a'] = true;
        total++;
      }

  for (int i = 0; i + 1 < wordsSize; i++) {
    const char *a = words[i], *b = words[i + 1];
    int la = strlen(a), lb = strlen(b);
    int len = la < lb ? la : lb;
    int j = 0;
    while (j < len && a[j] == b[j])
      j++;

    if (j == len) {
      if (la > lb)
        return strdup(""); // b is a proper prefix of a: invalid
      continue;
    }
    int u = a[j] - 'a', v = b[j] - 'a';
    if (!edge[u][v]) { // avoid double-counting
      edge[u][v] = true;
      indeg[v]++;
    }
  }

  // Kahn's algorithm; the queue never holds more than 26 letters in total
  int q[26], head = 0, tail = 0;
  for (int c = 0; c < 26; c++)
    if (seen[c] && indeg[c] == 0)
      q[tail++] = c;

  char *result = malloc(total + 1);
  int n = 0;
  while (head < tail) {
    int u = q[head++];
    result[n++] = 'a' + u;
    for (int v = 0; v < 26; v++)
      if (edge[u][v] && --indeg[v] == 0)
        q[tail++] = v;
  }
  result[n] = '\0';

  if (n != total) {
    result[0] = '\0';
  }
  return result;
}

269_solution2_postorder_dfs.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// Returns false if a cycle is found
static bool dfs(int u, bool edge[26][26], int *state, char *result, int *n) {
  state[u] = 1;
  for (int v = 0; v < 26; v++) {
    if (!edge[u][v])
      continue;
    if (state[v] == 1)
      return false; // back edge: cycle
    if (state[v] == 0 && !dfs(v, edge, state, result, n))
      return false; // propagate failure
  }
  state[u] = 2;
  result[(*n)++] = 'a' + u; // post-order
  return true;
}

char *foreignDictionary(char **words, int wordsSize) {
  bool seen[26] = {0};
  bool edge[26][26] = {{0}};
  int state[26] = {0}; // 0 = unvisited, 1 = visiting, 2 = done

  // 1. Register every letter
  for (int i = 0; i < wordsSize; i++)
    for (char *p = words[i]; *p; p++)
      seen[*p - 'a'] = true;

  // 2. Build edges (no in-degree needed)
  for (int i = 0; i + 1 < wordsSize; i++) {
    const char *a = words[i], *b = words[i + 1];
    int la = strlen(a), lb = strlen(b);
    int len = la < lb ? la : lb;
    int j = 0;
    while (j < len && a[j] == b[j])
      j++;

    if (j == len) {
      if (la > lb)
        return strdup("");
      continue;
    }
    edge[a[j] - 'a'][b[j] - 'a'] = true; // duplicates are harmless here
  }

  // 3. DFS from every unvisited letter
  char *result = malloc(27);
  int n = 0;
  for (int c = 0; c < 26; c++)
    if (seen[c] && state[c] == 0 && !dfs(c, edge, state, result, &n)) {
      result[0] = '\0';
      return result;
    }

  // 4. Post-order is reversed topological order
  for (int i = 0; i < n / 2; i++) {
    char t = result[i];
    result[i] = result[n - 1 - i];
    result[n - 1 - i] = t;
  }
  result[n] = '\0';
  return result;
}

269_solution1_kahn.cpp

#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  string foreignDictionary(vector<string> &words) {
    bool seen[26] = {};
    bool edge[26][26] = {};
    int indeg[26] = {};
    int total = 0;

    // 1. Register every letter that appears
    for (auto &w : words)
      for (char c : w)
        if (!seen[c - 'a']) {
          seen[c - 'a'] = true;
          total++;
        }

    // 2. Build edges from adjacent word pairs
    for (int i = 0; i + 1 < (int)words.size(); i++) {
      const string &a = words[i];
      const string &b = words[i + 1];
      auto [it1, it2] = mismatch(a.begin(), a.end(), b.begin(), b.end());

      if (it1 == a.end())
        continue; // a is prefix of b (or equal): fine
      if (it2 == b.end())
        return ""; // b is a proper prefix of a: invalid

      int u = *it1 - 'a', v = *it2 - 'a';
      if (!edge[u][v]) { // avoid double-counting
        edge[u][v] = true;
        indeg[v]++;
      }
    }

    // 3. Kahn's algorithm
    queue<int> q;
    for (int c = 0; c < 26; c++)
      if (seen[c] && indeg[c] == 0)
        q.push(c);

    string result;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      result += char('a' + u);
      for (int v = 0; v < 26; v++) {
        if (edge[u][v] && --indeg[v] == 0)
          q.push(v);
      }
    }

    // 4. Cycle check
    return (int)result.size() == total ? result : "";
  }
};

269_solution2_postorder_dfs.cpp

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
  bool seen[26] = {};
  bool edge[26][26] = {};
  int state[26] = {}; // 0 = unvisited, 1 = visiting, 2 = done
  string result;

  // Returns false if a cycle is found
  bool dfs(int u) {
    state[u] = 1;
    for (int v = 0; v < 26; v++) {
      if (!edge[u][v])
        continue;
      if (state[v] == 1)
        return false; // back edge: cycle
      if (state[v] == 0 && !dfs(v))
        return false; // propagate failure
    }
    state[u] = 2;
    result += char('a' + u); // post-order
    return true;
  }

public:
  string foreignDictionary(vector<string> &words) {
    // 1. Register every letter
    for (auto &w : words)
      for (char c : w)
        seen[c - 'a'] = true;

    // 2. Build edges (no in-degree needed)
    for (int i = 0; i + 1 < (int)words.size(); i++) {
      const string &a = words[i];
      const string &b = words[i + 1];
      auto [it1, it2] = mismatch(a.begin(), a.end(), b.begin(), b.end());

      if (it1 == a.end())
        continue;
      if (it2 == b.end())
        return "";

      edge[*it1 - 'a'][*it2 - 'a'] = true; // duplicates are harmless here
    }

    // 3. DFS from every unvisited letter
    for (int c = 0; c < 26; c++)
      if (seen[c] && state[c] == 0 && !dfs(c))
        return "";

    // 4. Post-order is reversed topological order
    reverse(result.begin(), result.end());
    return result;
  }
};

269_solution1_kahn.go

package graphs

func foreignDictionary(words []string) string {
    var seen [26]bool
    var edge [26][26]bool
    var indeg [26]int
    total := 0

    for _, w := range words {
        for i := 0; i < len(w); i++ {
            if !seen[w[i]-'a'] {
                seen[w[i]-'a'] = true
                total++
            }
        }
    }

    for i := 0; i+1 < len(words); i++ {
        a, b := words[i], words[i+1]
        n := min(len(a), len(b))
        j := 0
        for j < n && a[j] == b[j] {
            j++
        }

        if j == n {
            if len(a) > len(b) {
                return "" // b is a proper prefix of a: invalid
            }
            continue
        }
        u, v := a[j]-'a', b[j]-'a'
        if !edge[u][v] { // avoid double-counting
            edge[u][v] = true
            indeg[v]++
        }
    }

    // Kahn's algorithm
    q := []int{}
    for c := 0; c < 26; c++ {
        if seen[c] && indeg[c] == 0 {
            q = append(q, c)
        }
    }

    result := []byte{}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        result = append(result, byte('a'+u))
        for v := 0; v < 26; v++ {
            if edge[u][v] {
                indeg[v]--
                if indeg[v] == 0 {
                    q = append(q, v)
                }
            }
        }
    }

    if len(result) != total {
        return ""
    }
    return string(result)
}

269_solution2_postorder_dfs.go

package graphs

func foreignDictionary(words []string) string {
    var seen [26]bool
    var edge [26][26]bool
    var state [26]int // 0 = unvisited, 1 = visiting, 2 = done
    result := []byte{}

    // Returns false if a cycle is found
    var dfs func(u int) bool
    dfs = func(u int) bool {
        state[u] = 1
        for v := 0; v < 26; v++ {
            if !edge[u][v] {
                continue
            }
            if state[v] == 1 {
                return false // back edge: cycle
            }
            if state[v] == 0 && !dfs(v) {
                return false // propagate failure
            }
        }
        state[u] = 2
        result = append(result, byte('a'+u)) // post-order
        return true
    }

    // 1. Register every letter
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            seen[w[i]-'a'] = true
        }
    }

    // 2. Build edges (no in-degree needed)
    for i := 0; i+1 < len(words); i++ {
        a, b := words[i], words[i+1]
        n := min(len(a), len(b))
        j := 0
        for j < n && a[j] == b[j] {
            j++
        }

        if j == n {
            if len(a) > len(b) {
                return ""
            }
            continue
        }
        edge[a[j]-'a'][b[j]-'a'] = true // duplicates are harmless here
    }

    // 3. DFS from every unvisited letter
    for c := 0; c < 26; c++ {
        if seen[c] && state[c] == 0 && !dfs(c) {
            return ""
        }
    }

    // 4. Post-order is reversed topological order
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return string(result)
}

269_solution1_kahn.java

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public String foreignDictionary(String[] words) {
        boolean[] seen = new boolean[26];
        boolean[][] edge = new boolean[26][26];
        int[] indeg = new int[26];
        int total = 0;

        for (String w : words)
            for (char c : w.toCharArray())
                if (!seen[c - 'a']) {
                    seen[c - 'a'] = true;
                    total++;
                }

        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int len = Math.min(a.length(), b.length());
            int j = 0;
            while (j < len && a.charAt(j) == b.charAt(j))
                j++;

            if (j == len) {
                if (a.length() > b.length())
                    return ""; // b is a proper prefix of a: invalid
                continue;
            }
            int u = a.charAt(j) - 'a', v = b.charAt(j) - 'a';
            if (!edge[u][v]) { // avoid double-counting
                edge[u][v] = true;
                indeg[v]++;
            }
        }

        // Kahn's algorithm
        Queue<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < 26; c++)
            if (seen[c] && indeg[c] == 0)
                q.offer(c);

        StringBuilder result = new StringBuilder();
        while (!q.isEmpty()) {
            int u = q.poll();
            result.append((char) ('a' + u));
            for (int v = 0; v < 26; v++)
                if (edge[u][v] && --indeg[v] == 0)
                    q.offer(v);
        }

        return result.length() == total ? result.toString() : "";
    }
}

269_solution2_postorder_dfs.java

class Solution {
    private final boolean[] seen = new boolean[26];
    private final boolean[][] edge = new boolean[26][26];
    private final int[] state = new int[26]; // 0 = unvisited, 1 = visiting, 2 = done
    private final StringBuilder result = new StringBuilder();

    // Returns false if a cycle is found
    private boolean dfs(int u) {
        state[u] = 1;
        for (int v = 0; v < 26; v++) {
            if (!edge[u][v])
                continue;
            if (state[v] == 1)
                return false; // back edge: cycle
            if (state[v] == 0 && !dfs(v))
                return false; // propagate failure
        }
        state[u] = 2;
        result.append((char) ('a' + u)); // post-order
        return true;
    }

    public String foreignDictionary(String[] words) {
        // 1. Register every letter
        for (String w : words)
            for (char c : w.toCharArray())
                seen[c - 'a'] = true;

        // 2. Build edges (no in-degree needed)
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int len = Math.min(a.length(), b.length());
            int j = 0;
            while (j < len && a.charAt(j) == b.charAt(j))
                j++;

            if (j == len) {
                if (a.length() > b.length())
                    return "";
                continue;
            }
            edge[a.charAt(j) - 'a'][b.charAt(j) - 'a'] = true; // duplicates are harmless here
        }

        // 3. DFS from every unvisited letter
        for (int c = 0; c < 26; c++)
            if (seen[c] && state[c] == 0 && !dfs(c))
                return "";

        // 4. Post-order is reversed topological order
        return result.reverse().toString();
    }
}

269_solution1_kahn.js

/**
 * @param {string[]} words
 * @return {string}
 */
var foreignDictionary = function (words) {
  const adj = new Map(); // letter -> set of letters that must come after it
  const indeg = new Map();
  for (const w of words)
    for (const c of w)
      if (!adj.has(c)) {
        adj.set(c, new Set());
        indeg.set(c, 0);
      }

  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i];
    const b = words[i + 1];
    const len = Math.min(a.length, b.length);
    let j = 0;
    while (j < len && a[j] === b[j]) j++;

    if (j === len) {
      if (a.length > b.length) return ""; // b is a proper prefix of a: invalid
      continue;
    }
    if (!adj.get(a[j]).has(b[j])) { // avoid double-counting
      adj.get(a[j]).add(b[j]);
      indeg.set(b[j], indeg.get(b[j]) + 1);
    }
  }

  // Kahn's algorithm
  let q = [...indeg.keys()].filter((c) => indeg.get(c) === 0);
  let result = "";
  while (q.length > 0) {
    const next = []; // fresh array per level: Array.shift() is O(n)
    for (const u of q) {
      result += u;
      for (const v of adj.get(u)) {
        indeg.set(v, indeg.get(v) - 1);
        if (indeg.get(v) === 0) next.push(v);
      }
    }
    q = next;
  }

  return result.length === adj.size ? result : "";
};

269_solution2_postorder_dfs.js

/**
 * @param {string[]} words
 * @return {string}
 */
var foreignDictionary = function (words) {
  const adj = new Map(); // letter -> set of letters that must come after it
  const state = new Map(); // 0 = unvisited, 1 = visiting, 2 = done
  const result = [];

  // Returns false if a cycle is found
  const dfs = (u) => {
    state.set(u, 1);
    for (const v of adj.get(u)) {
      if (state.get(v) === 1) return false; // back edge: cycle
      if (state.get(v) === 0 && !dfs(v)) return false; // propagate failure
    }
    state.set(u, 2);
    result.push(u); // post-order
    return true;
  };

  // 1. Register every letter
  for (const w of words)
    for (const c of w)
      if (!adj.has(c)) {
        adj.set(c, new Set());
        state.set(c, 0);
      }

  // 2. Build edges (no in-degree needed)
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];
    const len = Math.min(a.length, b.length);
    let j = 0;
    while (j < len && a[j] === b[j]) j++;

    if (j === len) {
      if (a.length > b.length) return "";
      continue;
    }
    adj.get(a[j]).add(b[j]); // duplicates are harmless here
  }

  // 3. DFS from every unvisited letter
  for (const c of adj.keys()) if (state.get(c) === 0 && !dfs(c)) return "";

  // 4. Post-order is reversed topological order
  return result.reverse().join("");
};

269_solution1_kahn.py

from collections import deque
from typing import List


class Solution:
    def foreignDictionary(self, words: List[str]) -> str:
        adj = {c: set() for w in words for c in w}
        indeg = {c: 0 for c in adj}

        for a, b in zip(words, words[1:]):
            for x, y in zip(a, b):
                if x != y:
                    if y not in adj[x]:  # avoid double-counting
                        adj[x].add(y)
                        indeg[y] += 1
                    break
            else:
                if len(a) > len(b):
                    return ""  # b is a proper prefix of a: invalid

        # Kahn's algorithm
        q = deque(c for c in indeg if indeg[c] == 0)
        result = []
        while q:
            u = q.popleft()
            result.append(u)
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)

        return "".join(result) if len(result) == len(adj) else ""

269_solution2_postorder_dfs.py

from typing import List


class Solution:
    def foreignDictionary(self, words: List[str]) -> str:
        adj = {c: set() for w in words for c in w}  # 1. register every letter
        state = {c: 0 for c in adj}  # 0 = unvisited, 1 = visiting, 2 = done
        result = []

        # 2. Build edges (no in-degree needed)
        for a, b in zip(words, words[1:]):
            for x, y in zip(a, b):
                if x != y:
                    adj[x].add(y)  # duplicates are harmless here
                    break
            else:
                if len(a) > len(b):
                    return ""

        def dfs(u: str) -> bool:  # returns False if a cycle is found
            state[u] = 1
            for v in adj[u]:
                if state[v] == 1:
                    return False  # back edge: cycle
                if state[v] == 0 and not dfs(v):
                    return False  # propagate failure
            state[u] = 2
            result.append(u)  # post-order
            return True

        # 3. DFS from every unvisited letter
        for c in adj:
            if state[c] == 0 and not dfs(c):
                return ""

        # 4. Post-order is reversed topological order
        return "".join(reversed(result))

269_solution1_kahn.rs

use std::collections::VecDeque;

impl Solution {
    pub fn foreign_dictionary(words: Vec<String>) -> String {
        let mut seen = [false; 26];
        let mut edge = [[false; 26]; 26];
        let mut indeg = [0; 26];
        let mut total = 0;

        for w in &words {
            for &c in w.as_bytes() {
                let i = (c - b'a') as usize;
                if !seen[i] {
                    seen[i] = true;
                    total += 1;
                }
            }
        }

        for pair in words.windows(2) {
            let (a, b) = (pair[0].as_bytes(), pair[1].as_bytes());
            match a.iter().zip(b).position(|(x, y)| x != y) {
                None => {
                    if a.len() > b.len() {
                        return String::new(); // b is a proper prefix of a: invalid
                    }
                }
                Some(j) => {
                    let (u, v) = ((a[j] - b'a') as usize, (b[j] - b'a') as usize);
                    if !edge[u][v] {
                        // avoid double-counting
                        edge[u][v] = true;
                        indeg[v] += 1;
                    }
                }
            }
        }

        // Kahn's algorithm
        let mut q: VecDeque<usize> = (0..26).filter(|&c| seen[c] && indeg[c] == 0).collect();
        let mut result = String::new();
        while let Some(u) = q.pop_front() {
            result.push((b'a' + u as u8) as char);
            for v in 0..26 {
                if edge[u][v] {
                    indeg[v] -= 1;
                    if indeg[v] == 0 {
                        q.push_back(v);
                    }
                }
            }
        }

        if result.len() == total { result } else { String::new() }
    }
}

269_solution2_postorder_dfs.rs

impl Solution {
    pub fn foreign_dictionary(words: Vec<String>) -> String {
        let mut seen = [false; 26];
        let mut edge = [[false; 26]; 26];
        let mut state = [0u8; 26]; // 0 = unvisited, 1 = visiting, 2 = done
        let mut result = Vec::new();

        // 1. Register every letter
        for w in &words {
            for &c in w.as_bytes() {
                seen[(c - b'a') as usize] = true;
            }
        }

        // 2. Build edges (no in-degree needed)
        for pair in words.windows(2) {
            let (a, b) = (pair[0].as_bytes(), pair[1].as_bytes());
            match a.iter().zip(b).position(|(x, y)| x != y) {
                None => {
                    if a.len() > b.len() {
                        return String::new();
                    }
                }
                // duplicates are harmless here
                Some(j) => edge[(a[j] - b'a') as usize][(b[j] - b'a') as usize] = true,
            }
        }

        // 3. DFS from every unvisited letter
        for c in 0..26 {
            if seen[c] && state[c] == 0 && !Self::dfs(c, &edge, &mut state, &mut result) {
                return String::new();
            }
        }

        // 4. Post-order is reversed topological order
        result.reverse();
        String::from_utf8(result).unwrap()
    }

    // Returns false if a cycle is found
    fn dfs(u: usize, edge: &[[bool; 26]; 26], state: &mut [u8; 26], result: &mut Vec<u8>) -> bool {
        state[u] = 1;
        for v in 0..26 {
            if !edge[u][v] {
                continue;
            }
            if state[v] == 1 {
                return false; // back edge: cycle
            }
            if state[v] == 0 && !Self::dfs(v, edge, state, result) {
                return false; // propagate failure
            }
        }
        state[u] = 2;
        result.push(b'a' + u as u8); // post-order
        true
    }
}