솔루션: 외계인 사전 확인

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #953(쉬움): 외계인 사전 확인하기

설명:

(이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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 lexicographicaly in this alien language.

예:

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).

제약 조건:

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

아이디어:

(이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

여기서 순진한 접근 방식은 입력 배열(W)에서 연속된 단어 쌍을 반복하고 입력 알파벳(O)에서 각 문자의 위치를 ​​비교하여 불일치를 찾고 어떤 단어가 나오는지 결정할 수 있을 때까지 문자를 이동하는 것입니다. 먼저 사전적으로.

이것은 쉬운 질문이므로 이 방법은 작동하지만 시간 복잡도가 O(N * M * P)인 경우 N은 W의 길이, M은 W의 각 단어의 평균 길이, P는 길이입니다. 영형.

그러나 O에서 문자의 위치를 ​​반복적으로 찾는 대신 O(P)의 시간 복잡도에서 O(알파)에서 인덱스의 조회 테이블을 만들고 모든 위치 조회를 간단한 O(1) 연산으로 전환할 수 있습니다. 그러면 전체 시간 복잡도가 O(N * M + P)로 변경됩니다.

그런 다음 이전에 언급했듯이 W에서 단어 쌍(a, b)을 반복한 다음 해당 두 단어의 비교 문자(achar, bchar)를 반복하고 사전 색인(aix, bix)을 기반으로 평가할 수 있습니다.

aix < bix이거나 끝에 도달하면 두 단어가 올바른 사전순으로 되어 있으므로 다음 단어 쌍으로 이동해야 합니다. aix > bix이거나 b의 끝에 도달하면 두 단어가 올바른 사전 순서가 아니므로 false를 반환해야 합니다.

종료하지 않고 끝에 도달하면 true를 반환해야 합니다.

구현:

4개 언어 모두에 대한 코드에는 약간의 차이만 있습니다.

자바스크립트 코드:

(이동: Problem Description || Solution Idea )

var isAlienSorted = function(W, O) {
    let alpha = new Map([["",-1]])
    for (let i = 0; i < O.length; i++)
        alpha.set(O.charAt(i), i)
    for (let i = 1; i < W.length; i++) {
        let a = W[i-1], b = W[i]
        for (let j = 0; j < a.length; j++) {
            let achar = a.charAt(j), bchar = b.charAt(j),
                aix = alpha.get(achar), bix = alpha.get(bchar)
            if (aix < bix) break
            if (aix > bix) return false
        }
    }
    return true
};

파이썬 코드:

(이동: Problem Description || Solution Idea )

class Solution:
    def isAlienSorted(self, W: List[str], O: str) -> bool:
        alpha = {O[i]: i for i in range(len(O))}
        for i in range(1,len(W)):
            a, b = W[i-1], W[i]
            for j in range(len(a)):
                if j == len(b): return False
                achar, bchar = a[j], b[j]
                aix, bix = alpha[achar], alpha[bchar]
                if aix < bix: break
                if aix > bix: return False
        return True

자바 코드:

(이동: Problem Description || Solution Idea )

class Solution {
    public boolean isAlienSorted(String[] W, String O) {
        Map<Character,Integer> alpha = new HashMap<>();
        for (int i = 0; i < O.length(); i++)
            alpha.put(O.charAt(i), i);
        for (int i = 1; i < W.length; i++) {
            String a = W[i-1], b = W[i];
            for (int j = 0; j < a.length(); j++) {
                if (j == b.length()) return false;
                char achar = a.charAt(j), bchar = b.charAt(j);
                if (alpha.get(achar) < alpha.get(bchar)) break;
                if (alpha.get(achar) > alpha.get(bchar)) return false;
            }
        }
        return true;
    }
}

C++ 코드:

(이동: Problem Description || Solution Idea )

class Solution {
public:
    bool isAlienSorted(vector<string>& W, string O) {
        unordered_map<char,int> alpha;
        for (int i = 0; i < O.size(); i++)
            alpha[O[i]] = i;
        for (int i = 1; i < W.size(); i++) {
            string a = W[i-1], b = W[i];
            for (int j = 0; j < a.size(); j++) {
                if (j == b.size()) return false;
                char achar = a[j], bchar = b[j];
                if (alpha[achar] < alpha[bchar]) break;
                if (alpha[achar] > alpha[bchar]) return false;
            }
        }
        return true;
    }
};