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
[wrt,wrf,er,ett,rftt]55Example 2
[z,x,z]30Example 3
[abc,ab]20Build 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