953. Verifying An Alien Dictionary

Easy

Description

在一個外星語言中，字母表的順序由字串 order 定義。給定一組單字 words，判斷這些單字是否按照該外星字母表的順序排列。

Example:

Input: words = [“hello”,“leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz” Output: true

Intuition#

建立字母順序映射表，逐對比較相鄰單字是否符合順序。

將 order 轉為每個字母的優先順序 map
依序比較相鄰的兩個單字，找出第一個不同字母，檢查順序
若前面單字是後面的前綴且更長，則不符合順序

Approaches#

1: 建表逐對比較#

概念: 用陣列記錄每個字母的順序，然後依序比較相鄰單字的每個字元
時間複雜度: O(n * m)，n 為單字數，m 為單字最大長度
空間複雜度: O(1)（固定 26 大小的陣列）

class Solution {
    fun isAlienSorted(words: Array<String>, order: String): Boolean {
        val rank = IntArray(26)
        for (i in order.indices) {
            rank[order[i] - 'a'] = i
        }

        for (i in 0 until words.size - 1) {
            if (!inOrder(words[i], words[i + 1], rank)) return false
        }
        return true
    }

    private fun inOrder(w1: String, w2: String, rank: IntArray): Boolean {
        for (i in 0 until minOf(w1.length, w2.length)) {
            if (w1[i] != w2[i]) {
                return rank[w1[i] - 'a'] < rank[w2[i] - 'a']
            }
        }
        return w1.length <= w2.length
    }
}

⭐2: 簡潔寫法#

概念: 相同邏輯，利用 Kotlin 的 zip 簡化比較
時間複雜度: O(n * m)
空間複雜度: O(1)

class Solution {
    fun isAlienSorted(words: Array<String>, order: String): Boolean {
        val rank = IntArray(26)
        order.forEachIndexed { i, c -> rank[c - 'a'] = i }

        return words.asSequence().zipWithNext().all { (a, b) ->
            val diff = a.zip(b).firstOrNull { (x, y) -> x != y }
            if (diff != null) rank[diff.first - 'a'] < rank[diff.second - 'a']
            else a.length <= b.length
        }
    }
}

🔑 Takeaways#

Pattern: 自訂排序 – 建立字元優先順序映射
關鍵技巧: 只需比較相鄰對；注意前綴情況（“apple” vs “app” 是不合法的順序）