Leetcode: Verifying an Alien Dictionary

Verifying an Alien Dictionary



Similar Problems:


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.

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

Note:

  1. 1 <= words.length <= 100
  2. 1 <= words[i].length <= 20
  3. order.length == 26
  4. All characters in words[i] and order are english lowercase letters.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. A.length is even

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/verifying-an-alien-dictionary
// Basic Ideas: hashmap
// Complexity: Time O(n), Space O(1)
func isAlienSorted(words []string, order string) bool {
    m := map[rune]int{}
    for i, ch := range order { m[ch] = i }

    for i, q := range words {
        if i == 0 { continue }
        p := words[i-1]
        // compare p and q
        len_s := len(p)
        if len_s > len(q) { len_s = len(q) }

        j := 0
        for ; j<len_s; j++ {
            if m[rune(p[j])] > m[rune(q[j])] { 
                return false 
            } else {
                if m[rune(p[j])] < m[rune(q[j])] {
                    break
                }
            }
        }
        if j == len_s && len(p) > len(q) { return false }
    }
    return true
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.