力扣 953 验证外星语词典

题意：给定一个字母排序以及一个字符串array，查看字符串array是否按照字母顺序排序

思路：见代码注释

思想：Hashmap

复杂度：时间O（n^m)，空间O(256)

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] map = new int[256];
        // 用map记录字符的大小顺序
        for(int i=0;i<order.length();i++) {
            int cur = (int)order.charAt(i);
            map[cur] = i;
        }
        
        // 遍历words array查看是否是按顺序排列
        for(int i=1;i<words.length;i++) {
            if(!isOrder(words[i-1], words[i], map))
                return false; 
        }
        return true;
    }
    
    // 检查s1和s2是否按map的顺序排列
    boolean isOrder(String s1, String s2, int[] map) {
        int c1 = 0;
        int c2 = 0;
        // 遍历s1和s2，比较每一个字符
        while(c1 < s1.length() && c2 < s2.length()) {
            int temp1 = (int) s1.charAt(c1++);
            int temp2 = (int) s2.charAt(c2++);
            // s2的字符比s1小
            if(map[temp1]>map[temp2])
                return false;
            // s2的字符比s1大
            if(map[temp1]<map[temp2])
                return true;
        }
        // 对于apple,app这种
        if(c1 < s1.length())
            return false;
        return true;
    }
}