953. Verifying an Alien Dictionary

Description

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Constraints

• 1 <= words.length <= 100

• 1 <= words[i].length <= 20

• order.length == 26

• All characters in words[i] and order are English lowercase letters.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

Output: true

Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"

Output: false

Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"

Output: false

Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Solutions

Solution 1

/**
 * Time complexity : O(M), M be the total number of characters in words.
 * Space complexity : O(1)
 */

class Solution {
    private final int[] alienAlphaTable = new int[26];
    
    public boolean isAlienSorted(String[] words, String order) {
        if(words == null || words.length <= 1) {
            return true;
        }
        for(int i = 0; i < 26; i++) {
            alienAlphaTable[order.charAt(i)-'a'] = i;
        }
        for(int i = 0; i < words.length-1; i++) {
            if(isBigger(words[i], words[i+1])) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isBigger(String word1, String word2) {
        int minLen = Math.min(word1.length(), word2.length());
        for(int i = 0; i < minLen; i++) {
            char ch1 = word1.charAt(i);
            char ch2 = word2.charAt(i);
            if(ch1 != ch2) {
                return alienAlphaTable[ch1-'a'] > alienAlphaTable[ch2-'a'];
            }
        }
        return word1.length() > word2.length();
    }
}

Follow up