[comprehensive pen test] sword finger offer II 114 Alien dictionary

Title Description

This is a LeetCode Upper The finger of the sword Offer II 114. Alien Dictionary , The difficulty is difficult .

Tag : 「 graph theory 」、「 A topological sort 」、「 Drawing 」、「 graph theory BFS」

There is an alien language using English letters , The alphabetical order of this language is different from that of English .

Given a list of strings words , As a dictionary of this language ,words The string in has Sorted alphabetically in the new language .

Please restore the known alphabetical order in this language according to the dictionary , and In alphabetical order array . If there is no legal alphabetical order , return "" . If there are more than one possible legal alphabetical order , Return to it Any one Order is enough .

character string s Dictionary order is less than character string t There are two situations ：

At the first different letter , If s The letters in this alien language are in the alphabetical order of t Before the middle letter , that  s The dictionary order of is less than t . If the previous min(s.length, t.length) The letters are the same , that s.length < t.length when ,s The dictionary order is also less than t .

Example 1：

 Input ：words = ["wrt","wrf","er","ett","rftt"]

 Output ："wertf"

Example 2：

 Input ：words = ["z","x"]

 Output ："zx"

Example 3：

 Input ：words = ["z","x","z"]

 Output ：""

 explain ： There is no legal alphabetical order , Therefore return  "" .

Tips ：

• words[i] It's only made up of lowercase letters

Drawing + A topological sort

For convenience , We call words by ws, Combine two strings at the same time a and b The lexicographic order relation between is abbreviated as 「 Relationship 」.

Because of the array length and each The maximum length of is , We can achieve a complexity of Algorithm of complexity .

First of all, it's easy to think of , We deal with every... From front to back , utilize ws The array itself is lexicographically sorted , And then through And The relationship between （ among For the range of ）, To build relationships between characters .

Concrete , When we define the characters Than Dictionary order should be small , It can be established from To The directed side of , At the same time, the statistics increase The degree of , increase The degree of .

When the drawing is completed , We are from all degrees to It's the beginning of （ It means that there are no characters smaller than the dictionary order of these characters ）, Run through the topology sorting ： stay BFS In the process , Constantly delete points （ Out of line points can be seen as removed from the graph ） And update the entry of the edge point of the deleted point , If there is a new entry of The point of , Then join the team .

Students who do not understand topological sorting can look at the front : Introduction to topological sorting of graph theory

If the number of final outgoing nodes and the total number equal , This is a topology diagram （ acyclic , There is no dictionary order conflict between characters ）, The order of leaving the team is the dictionary order , Otherwise there is a conflict , Return to empty string .

Code ：

class Solution {
    int N = 26, M = N * N, idx = 0, cnt = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] in = new int[N], out = new int[N];
    boolean[] vis = new boolean[26];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
        out[a]++; in[b]++;
    }
    public String alienOrder(String[] ws) {
        int n = ws.length;
        Arrays.fill(he, -1);
        for (int i = 0; i < n; i++) {
            for (char c : ws[i].toCharArray()) {
                if (!vis[c - 'a'] && ++cnt >= 0) vis[c - 'a'] = true;
            }
            for (int j = 0; j < i; j++) {
                if (!build(ws[j], ws[i])) return "";
            }
        }
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < 26; i++) {
            if (vis[i] && in[i] == 0) d.addLast(i);
        }
        StringBuilder sb = new StringBuilder();
        while (!d.isEmpty()) {
            int u = d.pollFirst();
            sb.append((char)(u + 'a'));
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (--in[j] == 0) d.addLast(j);
            }
        }
        return sb.length() == cnt ? sb.toString() : "";
    }
    boolean build(String a, String b) {
        int n = a.length(), m = b.length(), len = Math.min(n, m);
        for (int i = 0; i < len; i++) {
            int c1 = a.charAt(i) - 'a', c2 = b.charAt(i) - 'a';
            if (c1 != c2) {
                add(c1, c2);
                return true;
            }
        }
        return n <= m;
    }
}

• Time complexity ： Make Is an array ws The length of , The complexity of counting the number of characters is , The complexity of drawing construction is ; Run topological order to build answer complexity . The overall complexity is
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series The finger of the sword Offer II 114 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be accessed from the smart typesetting Gather new bases