[Java] LeetCode 953 : Verifying an Alien Dictionary

LeetCode # 953

---

 

 

Example 1:

 

Input:
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

 

Example 2:

 

Input:
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters.

 

---

 

Solution #1 (1ms)

class Solution {
    int index = 0;
    Map<Character, Integer> map = new HashMap<>();

    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }
        map.put(' ', -1);

        while (true) {
            if (index == words.length - 1) return true;
            if (isSorted(words[index], words[index + 1])) {
                index++;
            } else {
                return false;
            }
        }
    }

    private boolean isSorted(String o1, String o2) {
        char[] lastArray = o1.toCharArray();
        char[] newArray = o2.toCharArray();

        int length = Math.max(lastArray.length, newArray.length);

        for (int i = 0; i < length; i++) {
            char last_char = i < lastArray.length ? lastArray[i] : ' ';
            char new_char = i < newArray.length ? newArray[i] : ' ';

        
            if (map.get(last_char) < map.get(new_char)) return true;
            else if(map.get(last_char) > map.get(new_char)) return false;
        }

        return true;
    }
}

 

Result #1

 

 

---

 

Solution #2 (0ms)

class Solution {
    String mOrder;
    int index = 0;

    public boolean isAlienSorted(String[] words, String order) {
        this.mOrder = order;

        while (true) {
            if (index == words.length - 1) return true;
            if (isSorted(words[index], words[index + 1])) {
                index++;
            } else {
                return false;
            }
        }
    }

    private boolean isSorted(String o1, String o2) {
        char[] lastArray = o1.toCharArray();
        char[] newArray = o2.toCharArray();

        int length = Math.max(lastArray.length, newArray.length);

        for (int i = 0; i < length; i++) {
            char last_char = i < lastArray.length ? lastArray[i] : ' ';
            char new_char = i < newArray.length ? newArray[i] : ' ';

            if (mOrder.indexOf(last_char) < mOrder.indexOf(new_char)) return true;
            else if (mOrder.indexOf(last_char) > mOrder.indexOf(new_char)) return false;
        }

        return true;
    }
}

 

Result #2

 

💡 Solution #1 에서 Map<?, ?> 자료형 대신에 String.indexOf() 메소드를 사용한다.

 

 

 

---

 

More Algorithm!

 

👇👇

 

github.com/ggujangi/ggu.leet-code

ggujangi/ggu.leet-code

 

 

 

 

출처 : leetCode