[Leetcode] 953. Verifying an Alien Dictionary - hash map

1. 문제링크

Verifying an Alien Dictionary - LeetCode

 

 

2. 문제 파악하기

먼저 이 주옥같은 문제는 이해하는데 조금 시간이 걸렸다

나만 이해못했나 해서 discussion에 들어가서 봤는데

문제를 이해하지 못한 사람도 많고 난이도가 맞지 않다는 의견이 대다수였다

 

그런데 실제로 사전 구조를 생각해보면 그렇게 어렵지 않다

 

실제로 "apple"와 "app"을 종이사전에서 찾아보면

"app"이 앞에 위치하고 있고 "apple"이 "app"보다 뒤에 위치하고 있다

words의 단어들이 사전상 순서대로 나열되어있는가? 가 문제이다

 

우리는 "abcd...z"라는 알파벳 순서로 찾지만

주옥같은 외계인의 언어에서는 저 순서가 아니라 order 순서를 따르는 것이다

 

 

3. 문제 해결하기 - hash map

맵에 각 알파벳의 index를 캐시해두고 사전상 순서를 비교한다

 

 

4. solution

class Solution {
public:
    bool correctOrder(unordered_map<char, int> &m, string a, string b){
        int size = min(a.size(), b.size());
        
        for(int i = 0; i < size; i++){
            if(m[a[i]] < m[b[i]]) 
                return true;
            else if(m[a[i]] > m[b[i]])  
                return false;
        }

        if(a.size() > b.size())
            return false;
        
        return true;
    }
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> m;
        for(int i = 0; i < order.size(); i++){
            m[order[i]] = i;
        }
        for(int i =0; i < words.size()-1; i++){
            if(!correctOrder(m, words[i], words[i+1]))
                return false;
        }
        return true;
    }
};