LeetCode 953: Verifying an Alien Dictionary Solution

Master LeetCode problem 953 (Verifying an Alien Dictionary), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

953. Verifying an Alien Dictionary

Easy

Array Hash Table String

Problem Explanation

Explanation

To solve this problem, we need to compare each pair of adjacent words in the input list to check if they are sorted lexicographically according to the given alien language order. We can do this by iterating through the words list and comparing each pair of words character by character.

Create a hashmap to store the order of each character in the alien language.
Compare each pair of adjacent words in the input list character by character.
If we find a character in the current word that is greater than the corresponding character in the next word, return false.
If all characters match until the end of the current word and the next word is shorter, return false.
If we finish iterating through all words and all characters are in the correct order, return true.

Time Complexity

The time complexity of this approach is O(C), where C is the total number of characters in all words.

Space Complexity

The space complexity of this approach is O(1) since we are using a fixed size hashmap of size 26 for the alien language characters.

Solution Code

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] map = new int[26];
        for (int i = 0; i < order.length(); i++) {
            map[order.charAt(i) - 'a'] = i;
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            
            int j = 0;
            while (j < word1.length() && j < word2.length()) {
                if (map[word1.charAt(j) - 'a'] < map[word2.charAt(j) - 'a']) {
                    break;
                } else if (map[word1.charAt(j) - 'a'] > map[word2.charAt(j) - 'a']) {
                    return false;
                }
                j++;
            }
            
            if (j == word2.length() && word1.length() > word2.length()) {
                return false;
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 953 (Verifying an Alien Dictionary)?

This page provides optimized solutions for LeetCode problem 953 (Verifying an Alien Dictionary) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 953 (Verifying an Alien Dictionary)?

The time complexity for LeetCode 953 (Verifying an Alien Dictionary) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 953 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 953 in Java, C++, or Python.

Back to LeetCode Solutions