[Easy] 953. Verifying an Alien Dictionary

문제

Easy

2841940Add to ListShare

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

 

외계인들의 언어는 놀랍게도, 영어 소문자를 사용하지만 다른 순서를 갖고 있다. 알파벳의 순서는 소문자들의 어떠한 순열이다. 

외계어로 쓰여진 words와 알파벳의 순서가 주어지면, 주어진 단어들이 이 외계어로 사전적으로 정렬되어 있는 경우에 true를 반환한다.

 

예시

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.

Example 3:

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 (More info).

 

제약 조건

Constraints:

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

 

풀이 과정

처음 문제를 봤을 때, 문제 자체를 이해하는 데에 시간이 좀 걸렸다.

그래도 해결할 수 있어 무척 기쁘다!

• 외계인 알파벳 순서를 map 객체에 저장한다.
• word의 개수만큼 for문을 돈다.
  • prev, curr 값을 지정한다.
  • 만약 prev, curr값이 같다면 다음 for문을 진행한다.
  • prev의 첫번째 값과 curr의 첫번째 값을 비교한다. 알파벳 순서가 prev가 더 클 경우, false를 반환한다.
  • prev의 첫번재 값과 curr의 첫번째 값이 같을 경우, while문을 순회한다.
    • prev의 값과 curr의 값이 같지 않을 때의 인덱스(p)를 찾는다. 만약 없을 경우, curr이나 prev의 길이를 넘지 않도록 조건을 지정한다.
    • curr[p]의 값이 undefined라면 prev의 길이가 더 긴 것이니 false를 반환한다.
    • prev[p]의 알파벳 순서와 curr[p] 알파벳 순서 중 prev가 더 크다면 false 를 반환한다.
  • for문의 진행이 끝나면, false에 해당하는 값이 없으므로 true를 반환한다.

풀이 코드

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
    const map = {};
    for(let i = 0 ; i < 26 ; i++){
        map[order[i]] = i;
    }
    
    for(let i = 1 ; i < words.length ; i++){
        let prev = words[i - 1]
        let curr = words[i]
        
        if(prev === curr) continue;
        
        if(map[prev[0]] > map[curr[0]]) return false;
        else if(prev[0] === curr[0]){
            let p = 1;
            while(prev[p] === curr[p] && p < Math.max(curr.length, prev.length)){                
                p++;
            }
            if(curr[p] === undefined) return false;
            if(map[prev[p]] > map[curr[p]]) return false;
        }            
    }
    return true;
};