Alien Dictionary LeetCode Həll

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Airbnb Amazon alma Bloomberg ByteDance Kupanq eBay Facebook Flipkart google microsoft Pinterest Snapchat cuqquldamaq Über VMware
RubirkBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Alien Dictionary LeetCode Solution – İngilis əlifbasından istifadə edən yeni bir yad dil var. Bununla belə, məktublar arasındakı sıra sizə məlum deyil.

Sizə sətirlərin siyahısı verilir words sətirlərin daxil olduğu yad dilin lüğətindən words var leksikoqrafik olaraq sıralanır bu yeni dilin qaydaları ilə.

Qayıtmaq sıralanmış yeni yad dildə unikal hərflər silsiləsi leksikoqrafik cəhətdən artan sıra yeni dilin qaydaları ilə. Çözüm yoxdursa, geri qayıdın "". Bir neçə həll yolu varsa, geri qaytarın onlardan hər hansı biri.

Bir simli s is leksikoqrafik cəhətdən daha kiçikdir simdən daha çox t birinci hərfdə fərqlənirlərsə, hərf içərisindədir s daxil olan hərfdən əvvəl gəlir t yad dildə. Əgər birinci min(s.length, t.length) onda hərflər eynidir s yalnız və yalnız o halda kiçikdir s.length < t.length.

misal

Test işi 1:

Input:

sözlər = [“wrt”, “wrf”, “er”, “ett”, “rftt”]

Çıxış:

"vertf"

Test işi 2:

Input:

sözlər = [“z”, “x”, “z”]

Çıxış:

""

Izahat

i) Birinci sınaq vəziyyətində “wertf” düzgün sətir ola bilər.

ii) İkinci sınaq vəziyyətində sifariş etibarsızdır, ona görə də “” qaytarın.

Yanaşma:

Əvvəlcə problem ifadəsini anlayaq

  1. sözlər sıralanır leksikoqrafik cəhətdən yəni əgər W[i] əvvəl lüğətdə görünür W[j] üçün i < j.
  2. Qeyd edək ki, individual words are not sorted. Əgər abcde əvvəl görünür abpqrst bu o demək deyil b əvvəl görünür a.

Qeyd edilməli əsas şeylər:

1. Sözlər lüğətində hər hansı iki ardıcıl söz üçün sıra birinci qeyri-adi işarəyə baxmaqla müəyyən edilir.

2. Qeyri-adi simvoldan sonra gələn simvolları heç bir ardıcıllıqla yekunlaşdırmaq üçün etibar etmək olmaz. Səbəb sözlər arasındakı ardıcıllığın sırf ilk uyğunsuzluq simvoluna əsaslanaraq qərarlaşdırıldığı üçün ondan sonrakı hər hansı simvol yalnız tam sözü təşkil edir.

3. Hər hansı bir sözdə görünən ardıcıl simvolların sıra ilə heç bir əlaqəsi yoxdur, lakin onlar yalnız tam sözü yaratmaq üçün oradadırlar.

Yanaşma:

1. Qrafik yaradın: Yuxarıdakı nöqtələrdən istifadə edərək, biz ardıcıl söz cütləri arasında təkrar edirik və kənarlar yaratmağa çalışırıq.

2. Topoloji Sort: Bu, DFS və ya istifadə etməklə edilə bilər BFS. Mən burada BFS ilə getməyə qərar verdim

Kənar hallarda

  1. ["abc", "ab"] – etibarlı lüğət deyil, əgər W[i] < W[j] sonra lüğətdə W[j] ola bilməz prefix of W[i]. belə ki, bu halda sadəcə olaraq boş bir sətir qaytarın.
  2. ["a", "b", "a"] – burada bu girişdə, a < b və b < aHansı bir dövrü. lüğətdə dövr ola bilməz.

Yadplanetli lüğəti üçün kod

C ++ Proqramı

class Solution {
public:
    // Finds the topological order of a directed Acyclic graph
    string topologicalSortBFS(unordered_map<char, unordered_set<char>> &g) {
        unordered_map<char, int> indegree;
        queue<char> q;
        // topological order
        string order;
        
        // Compute the indegree of each node
        for(auto u: g) {
            char src = u.first;
            for(auto neighbor: g[src]) 
                ++indegree[neighbor];
        }
        
        // if current has no dependency, add and mark as visited
        for(auto u: g) {
            char src = u.first;
            if(!indegree[src]) {
                q.emplace(src);
            }
        }
        // BFS traversal wrt to indegree of each node
        while(!q.empty()) {
            auto curr = q.front();
            q.pop();
            order += curr;
            
            // reduce the indegree of its neighbors
            for(auto neighbor: g[curr]) {
                --indegree[neighbor];
                if(!indegree[neighbor]) 
                    q.emplace(neighbor);
            }
        }
        return order.size() < g.size() ? "" : order;
    }
    
    string alienOrder(vector<string>& words) {
        // create a graph
        // To create a graph using the lexographic order,
        // we need to look at the consecutive word pairs and 
        // within the common length check for diff chars at the same
        // index position, each unequal pair is a directed edge coming
        // from words[i][j] to words[i+1][j]
        unordered_map<char, unordered_set<char>> g;
        // initialize the graph with nodes req
        for(auto &word: words)
            for(char &ch: word)
                if(!g.count(ch))
                    g[ch] = unordered_set<char>();
        
        // Imp: Add all the seen chars to graph even with 0 edges
        for(int w = 0; w + 1 < words.size(); w++) {
            int common_len = min(words[w].size(), words[w+1].size());
            // check if the lexographic order is being followed or not
            // P.S I dont think this case is even valid acc to problem description
            // Eg: ["abc", "ab"] -> Invalid
            if(words[w+1].size() < words[w].size() 
               && words[w].substr(0, common_len) == words[w+1])
                return "";
            
            for(int i = 0; i < common_len; i++) {
                // prevent self loop
                char src = words[w][i], dst = words[w+1][i];
                // If current pos has diff chars, then make an edge and
                // break since, the current word ordering was due this positional char
                // change and anything beyond this might not follow actual order.
                if(src != dst) {
                    g[src].emplace(dst);
                    break;
                }
            }
        }
        
        string order = topologicalSortBFS(g);
        return order;
    }
};

Java Proqramı

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> dict = new HashMap<>();
        Map<Character, Boolean> visited = new HashMap<>();
        
    // add character to visited map, mark all of them as unvisited
        for (String str: words) {
            for (char ch: str.toCharArray()) {
                visited.put(ch, false);
            }
        }
    
    // 
        for (int i = 0; i < words.length-1; i++) {
            if(!fillDict(dict, words[i], words[i+1])) {
                // invalid input, ex:- ab,abc is not a valid dictionary word
                return "";
            }
        }

        StringBuilder builder = new StringBuilder();
        for (char ch: visited.keySet()) {
            if (!visited.get(ch)) {
                // do the topological sorting from each unvisited dictionary character
                if (!topological(dict, ch, visited, new HashSet<>(), builder)) {
                    // loop detected. topological sort can not be performed in graph with cycle
                    return "";
                }
            }
        }
        return builder.reverse().toString();
    }
    
    private boolean topological(Map<Character, Set<Character>> dict, char ch,
                               Map<Character, Boolean> visited,
                               Set<Character> dfsStack, StringBuilder builder) {
        if (dfsStack.contains(ch)) {
            // oops!! loop detected
            return false;
        }
        if (visited.get(ch)) {
            return true;
        }
        visited.put(ch, true);
        dfsStack.add(ch);
        for (char c : dict.getOrDefault(ch, new HashSet<>())) {
            if (!topological(dict, c, visited, dfsStack, builder)) {
                return false;
            }
        }
        builder.append(ch);
        dfsStack.remove(ch);
        return true;
    }
    
    private boolean fillDict(Map<Character, Set<Character>> dict, String a, String b) {
        for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                dict.computeIfAbsent(a.charAt(i), x -> new HashSet<>()).add(b.charAt(i));
                return true;
            }
        }
        // minimum word is prefix of larger word, make sure word with less length comes before larger word
        // why? because if one string is prefix of another then prefix must come before string for example,
        // we are here becasue a,b = "abc" or "ab", since a is lexicographically smaller than b then a must
        // be "ab" because "abc" can never come before "ab".
        return a.length() <= b.length(); 
    }
}

Alien Dictionary LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O(V + E)

Kosmik Mürəkkəblik: Qrafik yaratmaq üçün O(V + E).

Crack Sistemi Dizayn Müsahibələri
Translate »