Verifying an Alien Dictionary

The key idea

Problem

In an alien language that still uses the 26 English lowercase letters, the letters follow a different order. You are given a list of words words written in this alien language, and a string order that lists all 26 letters in the alien alphabet's order.

Return true if and only if the given words are sorted in increasing lexicographic order according to this new alien order. Otherwise return false.

Lexicographic order works the same way as in English, except the meaning of each letter's rank comes from order instead of the usual a to z. When comparing two words, look at the first position where they differ: the word with the lower-ranked letter at that position is smaller. If one word is a prefix of the other, the shorter word is smaller.

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters.

Examples

Complexity

Time: O(n * m) Space: O(1)

More String problems

• Find the Index of the First Occurrence in a StringEASY
• Length of Last WordEASY
• Longest Common PrefixEASY
• Repeated Substring PatternEASY
• Reverse String IIEASY
• String to Integer (atoi)MEDIUM
• Text JustificationHARD
• Zigzag ConversionMEDIUM