LeetCode 269 Alien Dictionary

LeetCode 269 Alien Dictionary

Link: leetcode.com/problems/al…

Method: Topological sort BFS

Time complexity: O(mn), where n represents the length of the words array and M represents the length of the longest word in words

Space complexity: O(1), mainly because they say that only lowercase letters are included, so both the representation of the graph and the Queue should be in the constant range

Idea: Based on the order of the letters given, it’s not hard to think of topological sorting for this description. Topological sorting is also a very basic part of the algorithm, which is nothing more than BFS plus a hash table of entry. The main difficulty of this problem is how to construct this graph correctly. The idea is to scan the array with an index, and then compare it each time with the next string, because the first string has a higher lexicographical order than the last string, so the two characters can be directly compared to the first different character, the lexicographical relationship between the pair of characters. For example,” WRT “,” WRF “, we have a pointer to find the third bit, so obviously t comes before F, so we can put F in the child of T. One of the more painful aspects of this problem is that the data given may not be valid and may not be constructed at all. So add a line of code:

if (index == words[i + 1].length() && index < words[i].length()) { return null; }
Copy the code

You scan these two strings, and it turns out that the latter string is a prefix of the previous string, and then the latter string is longer than the latter string, like “ABC” before “A”, which doesn’t make sense. In this case, we use return NULL. If the graph is null, we assume that something was wrong with the composition, and return an empty string indicating that the input data cannot be used.

Code:

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = createGraph(words);
        return topologySort(graph);
    }
    
    private String topologySort(Map<Character, Set<Character>> graph) {
        if (graph == null) {
            return "";
        }
        
        Map<Character, Integer> in = new HashMap<>();
        for (Character key : graph.keySet()) {
            if(! in.containsKey(key)) { in.put(key,0);
            }
            Set<Character> child = graph.get(key);
            for (Character c : child) {
                int tmp = in.getOrDefault(c, 0) + 1;
                in.put(c, tmp);
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (Character key : in.keySet()) {
            if (in.get(key) == 0) { queue.offer(key); }}while(! queue.isEmpty()) { Character head = queue.poll(); cnt++; sb.append(head);for (Character neighbor : graph.get(head)) {
                int tmp = in.get(neighbor) - 1;
                in.put(neighbor, tmp);
                if (tmp == 0) { queue.offer(neighbor); }}}return cnt == graph.size() ? sb.toString() : "";
    }
    
    private Map<Character, Set<Character>> createGraph(String[] words) {
        Map<Character, Set<Character>> map = new HashMap<>();
        
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                if(! map.containsKey(c)) { map.put(c,newHashSet<Character>()); }}}for (int i = 0; i < words.length - 1; i++) {
            int index = 0;
            while (index < words[i].length() && index < words[i + 1].length()) {
                char cf = words[i].charAt(index);
                char cl = words[i + 1].charAt(index);
                if(cf ! = cl) { map.get(cf).add(cl);break;
                }
                index++;
            }
            if (index == words[i + 1].length() && index < words[i].length()) {
                return null; }}returnmap; }}Copy the code