Solution
Approach 1: Check Adjacent Words
Intuition
The words are sorted lexicographically if and only if adjacent words are. This is because order is transitive: a <= b
and b <= c
implies a <= c
.
Algorithm
Let's check whether all adjacent words a
and b
have a <= b
.
To check whether a <= b
for two adjacent words a
and b
, we can find their first difference. For example, "applying"
and "apples"
have a first difference of y
vs e
. After, we compare these characters to the index in order
.
Care must be taken to deal with the blank character effectively. If for example, we are comparing "app"
to "apply"
, this is a first difference of (null)
vs "l"
.
Complexity Analysis

Time Complexity: , where is the total content of
words
. 
Space Complexity: .
Analysis written by: @awice.