Verifying an Alien Dictionary
给一个String组, 给一个order. 检查String组是不是按照order已经排好序. 首先给order的字符一个rank, 然后依次比较字符串的字符.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { Map<Character, Integer> map = new HashMap<>(); public boolean isAlienSorted(String[] words, String order) { String[] s = words.clone(); // make a copy for(int i = 0 ; i < order.length(); i++) { map.put(order.charAt(i), i); // rank the char } Arrays.sort(words, new Comparator<String>() { //sort by ranking @Override public int compare(String o1, String o2) { for(int i = 0 ; i < Math.min(o1.length(), o2.length()); i++) { if(o1.charAt(i) != o2.charAt(i)) // if the char is diff, return map.get(o1.charAt(i)) - map.get(o2.charAt(i)); } return o1.length() - o2.length(); // in this case, all chars are match, but "apple" > "app", so return the longer one } }); for(int i = 0 ; i < words.length; i++) { if(!words[i].equals(s[i])) return false; } return true; } } |