Approach 1: Check Adjacent Words
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.
Let's check whether all adjacent words
a <= b.
To check whether
a <= b for two adjacent words
b, we can find their first difference. For example,
"apples" have a first difference of
e. After, we compare these characters to the index in
Care must be taken to deal with the blank character effectively. If for example, we are comparing
"apply", this is a first difference of
Time Complexity: , where is the total content of
Space Complexity: .
Analysis written by: @awice.