LeetCode 953. Verifying an Alien Dictionary (验证外星语词典)

题目标签：HashMap

　　题目给了我们一个 order 和 words array，让我们依照order 来判断 words array 是否排序。

　　利用hashmap 把order 存入 map，写一个helper method 来判断每临近的两个 word 是否排序正确。

　　遍历words array，依次比较临近的两个words。

　　具体看code。

Java Solution:

Runtime: 5 ms, faster than 64.55%

Memory Usage: 38.2 MB, less than 11.41%

完成日期：03/14/2019

关键点：把order 存入map

class Solution {

    public boolean isAlienSorted(String[] words, String order) {

        if(words.length == 1)

            return true;

        Map<Character, Integer> map = new HashMap<>();

        // put order into hashmap: key = char, value = index

        for(int i=0; i<order.length(); i++)

        {

            map.put(order.charAt(i), i);

        }

        // iterate words to compare each two

        for(int i=1; i<words.length; i++)

        {

            if(!isSorted(words[i-1], words[i], map))

                return false;

        }

        return true;

    }

    private boolean isSorted(String word1, String word2, Map map)

    {

        int size = Math.max(word1.length(), word2.length());

        for(int i=0; i<size; i++)

        {

            if(i >= word1.length())

                return true;

            else if(i >= word2.length())

                return false;

            int index1 = (int)map.get(word1.charAt(i));

            int index2 = (int)map.get(word2.charAt(i));

            if(index2 < index1)

                return false;

            else if(index1 < index2)

                return true;

        }

        return true;

    }

}

参考资料：N/A

LeetCode 题目列表 - LeetCode Questions List

题目来源：https://leetcode.com/

巴特西

LeetCode 953. Verifying an Alien Dictionary (验证外星语词典)

最新文章

热门文章