Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Proficient Level

Implement the alienDictionaryOrderSize method that returns the size of a valid alien character order.

You are given words sorted according to an unknown alien alphabet. Your task is to infer a valid ordering of characters from the word list.

Return the number of distinct characters in one valid ordering. If the ordering is impossible because of a cycle or invalid prefix case, return 0.

Example 1
Input:
words (string[]) = [wrt,wrf,er,ett,rftt]
size (int) = 5
Return:
(int) 5
Example 2
Input:
words (string[]) = [z,x,z]
size (int) = 3
Return:
(int) 0
Example 3
Input:
words (string[]) = [abc,ab]
size (int) = 2
Return:
(int) 0

Build ordering rules by comparing each pair of adjacent words.

The first position where two words differ gives a directed edge from the first word's character to the second word's character. If a longer word appears before its exact prefix, the input is invalid. After building edges, run topological sort. If all distinct characters are processed, return their count; otherwise a cycle exists.

This focuses on validating whether a consistent alphabet can be formed.

Pseudocode:

function alienDictionaryOrderSize(words, size):
    collect all distinct characters
    build empty graph and indegree map
    for i from 0 to size - 2:
        first = words[i]
        second = words[i + 1]
        if first starts with second and first is longer:
            return 0
        find first different character
        if found:
            add edge firstChar -> secondChar
            update indegree
    queue = all characters with indegree 0
    processed = 0
    while queue is not empty:
        char = remove front
        processed++
        for each next character:
            reduce indegree
            if indegree becomes 0:
                add to queue
    if processed != distinct character count:
        return 0
    return processed
Run your code to see the result.