在一個外星語言中，字母表的順序由字串
order定義。給定一組單字words，判斷這些單字是否按照該外星字母表的順序排列。
Example:
Input: words = [“hello”,“leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz” Output: true
Intuition
TIP
建立字母順序映射表，逐對比較相鄰單字是否符合順序。
- 將
order轉為每個字母的優先順序 map - 依序比較相鄰的兩個單字，找出第一個不同字母，檢查順序
- 若前面單字是後面的前綴且更長，則不符合順序
Approaches
1. Build Table, Pairwise Compare — O(n * m) / O(1)
- Idea: 用陣列記錄每個字母的順序，然後依序比較相鄰單字的每個字元
- Time:
O(n * m)，n 為單字數，m 為單字最大長度 - Space:
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. Concise — O(n * m) / O(1)
- Idea: 相同邏輯，利用 Kotlin 的
zip簡化比較 - Time:
O(n * m) - Space:
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: 自訂排序 — 建立字元優先順序映射
- Key trick: 只需比較相鄰對；注意前綴情況（“apple” vs “app” 是不合法的順序）