主題

LeetCode - 953. Verifying an Alien Dictionary 解題心得

Not In My Back Yard | 2021-02-23 00:00:03 | 巴幣 0 | 人氣 42

題目連結:


題目意譯:
在一個外星語言中,驚人地,他們也使用英文字母,但可能為不同的順序。字母表之順序為一個小寫字母之排列。

給定一個序列 words 其為外星語言寫成,以及字母表之順序,回傳真(True)若且唯若給定序列 words 有按照外星語言之字典序排列。

限制:
1 ≦ words.length ≦ 100
1 ≦ words[i].length ≦ 20
order.length == 26
words[i] 和 order 所有字元為英文小寫字母。



範例測資:
範例 1:
輸入: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
輸出: true
解釋: 因為該語言中 'h' 排在 'l' 前面,因此給定序列已排序。

範例 2:
輸入: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
輸出: false
解釋: 因為該語言中 'd' 排在 'l' 後面,則 words[0] > words[1],因此給定序列並未排序。

範例 3:
輸入: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
輸出: false
解釋: 前三個字元 "app" 都符合,而第二個字串較短(字元數)。根據字典序規則 "apple" > "app",因為 'l' > '∅',其中 '∅' 定義為空字元且其小於任何字元(更多資訊)。


解題思維:
先掃過一次字串 order,對於每個字元 order[i],因為前面可能排著其他的字母。因此我們將 order[i] 這個字母之「大小」S[order[i]] 設為 i,代表其字典序(應排在大小之值較小的字母後面)。

從 i = 1 開始,每次判斷 words[i - 1] 是否 ≦ words[i],而判斷之基準則是按照給定的 order。

對於兩個字串 A 、 B在這題的比較,會是:
令 length = min(A 的長度, B 的長度)
對於 i = 0 ~ length - 1
  如果 S[A[i]] < S[B[i]],則代表 A < B。
  如果 S[A[i]] > S[B[i]],則代表 A > B。
如果上面比完沒有分出勝負,則比較兩者字串長度
  如果 A 的長度 < B 的長度,則代表 A < B。
  如果 A 的長度 = B 的長度,則代表 A = B。
  如果 A 的長度 > B 的長度,則代表 A > B。

其實上面的比較就是典型的字典序判斷,但是換成自定義的字典順序(即給定的 order,也就是上面的 S)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作