[Java] LeetCode 953. Verifying an Alien Dictionary

[Java] LeetCode 953. Verifying an Alien Dictionary

 

문   제 : 

문자열들의 배열 words가 주어진다.

일반적인 사전적 순서가 아닌 재정의 된 사전 문자열 order가 주어진다.

words에 들어있는 단어들이 order에 따라 정렬되어 있는지 확인해라.

 

{ 1 <= words.length <= 100 }

{ 1 <= words[i].length <= 20 }

{ order.length == 26}

 

 

Example )

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

//////////////////////////////////////////////////////////

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: 
The first three characters "app" match, and the second string is shorter (in size.)
According to lexicographical rules "apple" > "app", 
because 'l' > '∅',
where '∅' is defined as the blank character which is less than any other character.

 

---

접   근 : 

사전에 나와있는 각 알파벳의 index를 기준으로 단어들이 정렬되어 있는지 확인한다.

---

해   결 : 

단어 2개를 비교하는 함수를 만든다. - solve

 

함수에서는 두 단어를 order에 따라 비교하게 된다.

 

두 단어의 첫 글자부터 비교하여 만약 글자가 다르다면, 바로 판별할 수 있다.

뒤에 오는 글자가 사전적으로 더 뒤에 나오면 true인 것이다.

 

그게 아니고 만약에 두 글자가 같다면, 그 다음 단어를 비교하게 된다.

이런식으로 더 짧은 단어의 끝까지 비교하게 된다.

 

만약 계속 두 단어가 같아서 return 에 걸리지 않았다면, 

상황은 두 가지로 볼 수 있다.

1. 두 단어가 완전히 일치           ex) "app", "app"

2. 두 단어가 상관관계에 위치    ex) "app", "apple"

 

두 가지 상황을 판별하는 방법은 간단하다.

두 단어의 길이를 보면 되는 것이다.

 

만약 두 단어의 길이가 같다면, 완전히 일치하는 단어이므로 true를 반환한다.

그렇지 않다면, 더 짧은 단어가 앞에 와야하므로 단어1의 길이가 단어2의 길이보다 짧으면 true를 반환해준다.

 

위 과정을 words에 있는 단어들에게 실행시켜 주면, 하나라도 false가 반환된다면 정렬되어 있지 않다고 볼 수 있다.

---

 

solve 함수 구현

public boolean solve(String word1, String word2, String order){
    // 두 단어 중 더 짧은 단어 기준
    int len = (word1.length() >= word2.length()) ? word2.length() : word1.length();
    int temp=0;

    for(int j=0; j<len; j++){
        if(order.indexOf(word1.substring(j, j+1)) < order.indexOf(word2.substring(j, j+1))){
            return true;
        }
        else if(order.indexOf(word1.substring(j, j+1)) == order.indexOf(word2.substring(j, j+1))){
            temp++;
        }
        else{
            return false;
        }
    }

    // 두 단어의 길이가 같고 계속 똑같으면
    if(temp == len && word1.length() == word2.length()) return true;

    // 두 단어가 포함관계에 있고 길이가 짧은게 먼저 나왔다면
    else if(temp == len && word1.length() < word2.length()) return true;

    return false;
}

 

 

---

결   과  :

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // 단어 1, 단어 2 비교 -> 첫 번째 인덱스 부터 끝까지 비교하는데 포함되는거면 짧은게 앞으로 와야함
        for(int i=0; i<words.length-1; i++){
            if(!solve(words[i], words[i+1], order)){
                return false;
            }
        }

        return true;
    }
    public boolean solve(String word1, String word2, String order){
        // 두 단어 중 더 짧은 단어 기준
        int len = (word1.length() >= word2.length()) ? word2.length() : word1.length();
        int temp=0;

        for(int j=0; j<len; j++){
            if(order.indexOf(word1.substring(j, j+1)) < order.indexOf(word2.substring(j, j+1))){
                return true;
            }
            else if(order.indexOf(word1.substring(j, j+1)) == order.indexOf(word2.substring(j, j+1))){
                temp++;
            }
            else{
                return false;
            }
        }

        // 두 단어의 길이가 같고 계속 똑같으면
        if(temp == len && word1.length() == word2.length()) return true;

        // 두 단어가 포함관계에 있고 길이가 짧은게 먼저 나왔다면
        else if(temp == len && word1.length() < word2.length()) return true;

        return false;
    }
}