LeetCode.953-驗證外語字典順序(Verifying an Alien Dictionary)

這是悅樂書的第364次更新，第392篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

226

題（順位題号是

953

）。在外語中，令人驚訝的是，他們也使用英文小寫字母，但可能使用不同的順序。字母表的順序是小寫字母的一些排列。

給定用外語編寫的單詞序列以及字母表的順序，當且僅當給定單詞在這種外來語言中按字典排序時才傳回true。

例1：

輸入：words = [“hello”，“leetcode”]，order =“hlabcdefgijkmnopqrstuvwxyz”

輸出：true

說明：由于'h'在此語言中位于'l'之前，是以序列已排序。

例2：

輸入：words = [“word”，“world”，“row”]，order =“worldabcefghijkmnpqstuvxyz”

輸出：false

說明：由于'd'在此語言中位于'l'之後，然後是單詞[0]>單詞[1]，是以序列未排序。

例3：

輸入：words = [“apple”，“app”]，order =“abcdefghijklmnopqrstuvwxyz”

說明：前三個字元

“app”

比對，第二個字元串更短（大小）。根據詞典規則

“apple”

>

“app”

，因為

'l'

'∅'

，其中

'∅'

定義為空白字元小于任何其他字元。

注意：

• 1 <= words.length <= 100
• 1 <= words [i] .length <= 20
• order.length == 26

• words[i]

  和

  order

  中的所有字元都是英文小寫字母。

02 第一種解法

題目的意思是給定一個自定義的字母排列順序，然後根據這個排列順序來判斷字元串數組中的字元串是不是順序排列的，是就傳回

true

，不是就傳回

false

。

正常的字母排列順序肯定是

abcde......xyz

這樣，但是題目給的不一定是這樣，是以需要先将字母順序建立起來，使用一個

HashMap

來存，記為

dict

，

key

為字母，

value

為字母所在的位置（在字元串

order

中的位置），接着開始處理words中的字元串。

我們依次比較相鄰的兩個字元串即可，對于前後兩字元串的長度關系，有兩種情況，兩者長度相等或者一長一短，取兩字元串長度中的較小值作為循環次數的上限，避免越界風險，并且後續還會用到這個較小的字元串長度。

擷取兩字元串目前字元在

dict

中的

value

值，并且做減法，如果兩字元所在的位置之差為0，說明字元相，繼續往下循環，指導不等于0。

如果兩字元所在的位置之差為-1，說明順序是對的，繼續處理下一批相鄰的字元串即可。

如果兩字元所在的位置之差大于0，即前一個字元串中的目前字元在後一個字元串中的目前字元之後，即後一個字元串應該在前，傳回

false

如果兩字元所在的位置之差等于0，即其中有個字元串短些，但是兩字元串長度的較小值不等于前一個字元串的長度，即短的字元串在後，傳回

false

，可以參見題目給的例子三。

public boolean isAlienSorted(String[] words, String order) {
    Map<Character, Integer> dict = new HashMap<Character, Integer>();
    for (int i=0; i<order.length(); i++) {
        dict.put(order.charAt(i), i);
    }
    int n = words.length;
    for (int i=0; i<n-1; i++) {
        int res = 0;
        String s = words[i], s2 = words[i+1];
        int j = s.length(), k = s2.length();
        int min = Math.min(j, k);
        // 隻有兩邊的字母相同，循環才會繼續執行
        for (int m=0; m < min && res == 0; m++) {
            res = dict.get(s.charAt(m))-dict.get(s2.charAt(m));
        }
        if (res > 0 || (res == 0 && min != j)) {
            return false;
        }
    }
    return true;
}
           

03 第二種解法

針對上面的解法，我們可以将

HashMap

換成

26

的整型數組，将比較單個字母前後位置的方法獨立了出來，其他思路都是一樣的。

public boolean isAlienSorted2(String[] words, String order) {
    int[] dict = new int[26]; 
    for (int i=0; i<order.length(); i++) {
        dict[order.charAt(i)-'a'] = i;
    }
    int n = words.length;
    for (int i=0; i<n-1; i++) {
        if (!compareTwoString(words[i], words[i+1], dict)) {
            return false;        
        }                
    }
    return true;
}

public boolean compareTwoString(String s, String s2, int[] dict){
    int i = s.length(), j = s2.length();
    int min = Math.min(i, j);
    int res = 0;
    for (int k=0; k<min && res == 0; k++) {
        res = dict[s.charAt(k)-'a'] - dict[s2.charAt(k)-'a'];
    }
    if (res > 0) {
        return false;
    }
    return res == 0 ? min==i : true;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章232+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！