面试算法34：外星语言是否排序

题目

有一门外星语言，它的字母表刚好包含所有的英文小写字母，只是字母表的顺序不同。给定一组单词和字母表顺序，请判断这些单词是否按照字母表的顺序排序。例如，输入一组单词[“offer”，“is”，“coming”]，以及字母表顺序"zyxwvutsrqponmlkjihgfedcba"，由于字母’o’在字母表中位于’i’的前面，因此单词"offer"排在"is"的前面；同样，由于字母’i’在字母表中位于’c’的前面，因此单词"is"排在"coming"的前面。因此，这一组单词是按照字母表顺序排序的，应该输出true。

分析

目前字母表的顺序由一个输入的字符串决定。在确定单词排序的顺序时，它们的每个字母在该字母表中的顺序至关重要。为了方便查找每个字母在字母表中的顺序，可以创建一个哈希表，哈希表的键为字母表的每个字母，而值为字母在字母表中的顺序。由于字母表中的字母数目是固定的，总共26个，因此可以用一个长度为26的数组来模拟哈希表，数组的下标对应哈希表的键，而数组的值对应哈希表的值。

解

public class Test {public static void main(String[] args) {String[] strs = {"offer", "is", "coming"};String order = "zyxwvutsrqponmlkjihgfedcba";boolean result = isAlienSorted(strs, order);System.out.println(result);}public static boolean isAlienSorted(String[] words, String order) {int[] orderArray = new int[order.length()];for (int i = 0; i < order.length(); i++) {orderArray[order.charAt(i) - 'a'] = i;}for (int i = 0; i < words.length - 1; i++) {if (!isSorted(words[i], words[i + 1], orderArray)) {return false;}}return true;}private static boolean isSorted(String word1, String word2, int[] order) {int i = 0;for (; i < word1.length() && i < word2.length(); i++) {char ch1 = word1.charAt(i);char ch2 = word2.charAt(i);if (order[ch1 - 'a'] < order[ch2 - 'a']) {return true;}if (order[ch1 - 'a'] > order[ch2 - 'a']) {return false;}}// 如果word1是短的，返回true;如果word1是长的，返回falsereturn i == word1.length();}
}