외계인 사전 문제

문제 설명

외계 언어의 문자 순서를 결정합니다. 귀하의 임무는 외계 언어의 유효한 주문을 반환하는 것입니다. 일반 사전에서 N개의 단어와 k개의 초기 알파벳으로 정렬된alien language dictionary이 주어집니다.

참고: 주어진 테스트 사례에 대해 많은 주문을 사용할 수 있으므로 유효한 주문을 반환할 수 있습니다.

제약

0 <= N (arr의 크기) <= 10^5
0 <= ARR[i].크기() <= 10^5
제한 시간: 1초

사례 사례

예 1
입력: N = 5, K = 4
사전 = {"baa","abcd","abca","cab","cad"}

출력: 1
설명: 여기서 문자의 순서는 'b', 'd', 'a', 'c'입니다. 단어가 정렬되고 주어진 언어에서 "baa"가 "abcd"앞에 오므로 'b'가 'a' 앞에 옵니다. 출력에서.

예 2
입력: N = 3, K = 3
사전 = {"caa","aaa","aab"}

출력: 1
설명: 여기서 문자 순서는 'c', 'a', 'b'입니다. 단어가 정렬되고 주어진 언어에서 "caa"가 "aaa"앞에 오므로 출력에서 ​​'c'가 'a' 앞에 옵니다.

해결책

토폴로지 정렬 및 순열 접근 방식을 사용하여 위의 문제를 해결할 것입니다.

접근법 1

순열 접근법(무차별 대입)

각 단어에 나타나는 고유 문자를 모두 찾습니다.

이러한 서로 다른 문자의 가능한 모든 조합을 생성합니다.

각 순열은 유효한 알파벳 순서로 처리되어야 합니다. 주어진 단어가 이 순서대로 배열되어 있는지 확인합니다. 이를 달성하기 위해 다음을 수행합니다.

ㅏ. 1에서 n - 1까지의 모든 단어에 대해 현재 단어를 'currWord'로 두고 다음 단어를 'nextWord'로 둡니다.
비. 두 단어의 문자를 하나씩 비교하여 일치하지 않는 첫 번째 문자를 찾습니다. 일치하지 않는 문자가 없으면 다음 단어로 이동합니다.
씨. 'currWord'와 'nextWord'에서 일치하지 않는 문자가 각각 'ch1'과 'ch2'라고 가정해 보겠습니다.
디. 이제 이 단어(currWord 및 nextWord)가 사전 뒤에 오는 경우 시퀀스에서 'ch1'이 'ch2' 앞에 나타납니다.

단어가 현재 순서에 따라 정렬된 경우 이 순서를 반환합니다.

암호

`bool checkOrder(문자열 *dict, int n, 벡터 &p)
{
unordered_map pos;

for (int i = 0; i < p.size(); i++)
{
    if (pos.find(p[i]) == pos.end())
    {
        pos[p[i]] = i;
    }
}

for (int i = 0; i < n - 1; i++)
{
    string currentWord = dict[i];
    string nextWord = dict[i + 1];

    for (int j = 0; j < min(currentWord.length(), nextWord.length()); j++)
    {
        if (currentWord[j] != nextWord[j])
        {
            if (pos.find(currentWord[j]) == pos.end() || pos.find(nextWord[j]) == pos.end() ||
                pos[nextWord[j]] < pos[currentWord[j]])
            {
                return false;
            }
            else
            {
                break;
            }
        }
    }

    if (currentWord.length() > nextWord.length())
    {
        return false;
    }
}

return true;

}

벡터 getAlienLanguage(string *dict, int n)
{
벡터 p;
unordered_set uniqChar;

for (int i = 0; i < n; ++i)
{
    for (char c : dict[i])
    {
        if (uniqChar.find(c) == uniqChar.end())
        {
            p.push_back(c);
        }

        uniqChar.insert(c);
    }
}

sort(p.begin(), p.end());

do
{
    if (checkOrder(dict, n, p))
    {
        return p;
    }

} while (next_permutation(p.begin(), p.end()));

return p;

}`

복잡성 분석

위의 접근 방식은 O(K! * N * L) 시간이 걸립니다. 여기서 K는 고유 문자 수, N은 사전에 있는 단어 수, L은 사전에 있는 단어의 최대 길이입니다. 이로 인해 TLE 오류가 발생합니다.

접근법 2

외계인 어휘 ["wrt", "wrf",....]의 처음 두 단어를 고려하면 문자의 첫 번째 불일치를 보면 발생 순서에 대한 중요한 정보를 얻을 수 있습니다!
즉, 우리는 위의 두 용어에서 't'가 'f'보다 먼저 온다고 주장할 수 있습니다! 이 관계는 문자 't'와 'f'로 표시됩니다.
방향 그래프를 사용하여 이 관계를 설명할 수 있습니다!
따라서,

결과적으로 모든 단어를 반복하여 앞서 언급한 관계를 나타내는 그래프를 만듭니다. 그래프의 꼭짓점은 모든 개별 문자가 되고 방향이 지정된 가장자리는 어떤 문자가 다른 문자 앞에 오는지 매핑하는 관계가 됩니다.

생성된 그래프에서 토폴로지 정렬을 수행하여 생성된 그래프의 잠재적인 순서 중 하나를 반환합니다.

암호
class Solution{
public:
void helper(vector<vector<int>> adj, string &ans, int x, vector<bool> &vis){
vis[x] = true;
char c = x + 'a';
for(auto z : adj[x] ){
if(!vis[z]){
helper(adj, ans, z, vis);
}
}
ans = c + ans;
}
string findOrder(string dict[], int N, int K) {
vector<vector<int>> adj(K);
for(int i=0; i<N-1; i++){
string a = dict[i], b = dict[i+1];
for(int j=0; j<min(a.size(),b.size()); j++){
if(a[j] != b[j]){
adj[a[j]-'a'].push_back(b[j]-'a');
break;
}
}
}
string s="";
vector<bool> vis(K, false);
for(int i=0; i<K; i++){
if(!vis[i]){
helper(adj, s, i, vis);
}
}
return s;
}
};
복잡성 분석

시간 복잡도는 O(N+ K)입니다. N은 사전에 있는 총 단어이고 K는 사전에 있는 개별 문자입니다.

토폴로지 정렬의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점 수이고 E는 가장자리 수이며 O(K + N)은 가장자리 수입니다.

공간 복잡도는 K개의 개별 문자를 저장하기 위해 O(K)가 됩니다.