Foreign Dictionary - JS Solution

JS
Editorial

Approach

  • We are given a list of words that are already sorted according to some alien dictionary, and we need to reconstruct a valid ordering of characters consistent with this sorting.
  • We model this as a graph / topological ordering problem over at most 26 lowercase letters:
    • We use a fixed-size dependenciesMap[alphabetIndex], where each entry is a set of characters that must come before the character corresponding to that index.
      Here, alphabetIndex represents the zero-based position of a lowercase English letter (e.g., 'a' → 0, 'b' → 1, …, 'z' → 25).
    • We use a state[alphabetIndex] array mapped in the same way — each entry corresponds to the same alphabetIndex as in dependenciesMap and tracks the DFS visit status of that character:
      • 0 — unvisited
      • 1 — currently visiting (part of the current DFS path)
      • 2 — fully processed (all dependencies resolved)
    • We maintain a result list where we append characters once all their dependencies are resolved.
  • Building the dependency rules from adjacent words:
    • The alien dictionary guarantees that the given words are already sorted according to the unknown alphabet order. Therefore, by comparing only adjacent words, we can deduce all necessary ordering relationships between characters — since if two words differ at an index, their relative order already reflects how their first differing characters must be ordered in the alien language.
    • For each pair of adjacent words, we scan from left to right to find the first position where they differ. Characters after this position have no effect on the ordering and are ignored for this comparison.
    • If we find differing characters firstChar and secondChar at index i, it means firstChar must come before secondChar in the alien order. This rule is recorded in dependenciesMap by adding firstChar as a dependency of secondChar.
    • Once this first differing position is found, any remaining characters in those words do not add new constraints, since their relative order is already determined by the earlier difference.
    • If no difference is found and the first word is longer than the second (for example, "abc" before "ab"), this violates lexicographic ordering rules — such a case is invalid, and we return an empty result immediately.
  • DFS over characters (dependency resolution & cycle detection):
    • For each character ch we encountered in dfs:
      • If state[ch] = 1, it means ch is already on the current DFS path — a cycle is detected. In this case, we prune this branch and return false to signal failure.
      • If state[ch] = 2, it was already fully processed in a previous DFS call, so we skip reprocessing and return true.
      • Otherwise, we begin processing ch:
        • We set state[ch] = 1 (“currently visiting”) to mark it as part of the current DFS path. Any revisit to a character with state = 1 along this path indicates a cycle, so we prune the DFS branch and return false to signal failure.
        • For each dependency pre in dependenciesMap[ch]:
          • We recursively perform DFS on pre to ensure that all characters which must come before ch are fully resolved first.
            • If any recursive DFS call returns false (indicating a cycle), we return false to propagate that failure upward without further exploration.
        • After all dependencies of ch are successfully processed, we set state[ch] = 2 (fully processed) and append ch to the result list, returning true to indicate successful completion of that DFS branch.
  • Global traversal over all characters:
    • We iterate over all characters appearing in the input words and invoke DFS on each (the DFS function itself handles skipping characters already marked as fully processed (state = 2) immediately).
      • If any DFS call returns false, it means a cycle was detected, so no valid alien ordering exists and the function returns an empty string.
    • If no DFS call fails, meaning that all reachable characters are processed without conflicts, the collected result sequence contains the alien characters in their correct order. We then join its contents into a string and return it.

Time Complexity

Let N be the total number of characters across all input words, and let C be the number of distinct letters (≤ 26).
Building the dependency rules from adjacent words takes O(N) time.
During DFS, each character is explored only once (aside from constant-time checks for those already fully processed or currently being visited on the DFS path), and the maximum recursion depth of any DFS call is bounded by C.
Thus, the total DFS workload across all unique characters (excluding immediate returns) is O(C²), and across all characters (including DFS calls that immediately return) is O(N + C²) in the worst case.
Combining both phases, the overall running time is O(N + C²), which simplifies to O(N) since C is a constant (≤ 26).

Space Complexity

We use a fixed-size dependenciesMap array of length 26, where each entry is a set holding characters that must appear before the corresponding alphabet letter. This structure can contain at most 26 × 26 relationships — a constant bound independent of input size.
The state array and result list are also fixed-size, each tracking at most 26 characters.
No additional data structures scale with the number of input words or characters beyond these constant-sized arrays.
Hence, the overall space complexity is O(1) with respect to the input size.