7.31

(a) Algorithm
1. Create a directed graph G whose α vertices correspond to the letters.
2. For each consecutive pair of words wi, wi+1 (i = 1 … n-1):
   a. Scan the two words left-to-right until the first index p at which their characters differ.
   b. Let c = wi[p] and d = wi+1[p]; add the directed edge c → d to G (meaning c comes before d).
   c. If no differing position exists and |w_i| > |w_i+1|, the input is inconsistent (a longer prefix cannot precede its own prefix).
3. Run a topological sort (e.g. Kahn’s BFS) on G. If the sort succeeds, the produced list is the alphabet order; a cycle means the input is contradictory.

// pseudocode
build_graph(words):
  for i = 0 … n-2:
    p = firstDifferent(words[i], words[i+1])
    if p ≠ -1:
      addEdge(words[i][p], words[i+1][p])
    else if len(words[i]) > len(words[i+1]):
      error // invalid ordering
  return topoSort()

(b) Running time
• Comparing each adjacent pair inspects at most k characters ⇒ O(nk).
• At most n−1 edges are inserted ⇒ O(n).
• Topological sort costs O(α + E) = O(α + n).
Overall complexity: O(nk + α).  (Space: O(α + n) for the graph and in-degree counts.)

Back to Chapter 7