Object oriented easily understandable solution in Java


  • 0
    S

    public class Solution {

    // class to represent a node
    private class Node
    {
        // list of neigbors of a node
        private  List<Node> neigbours = new ArrayList<>();
        // identify the character
        char val;
        // incoming edge count
        int incoming = 0;
    
        public Node(char c)
        {
            val=c;
        }
    }
    
    Map<Character,Node> maps = new HashMap();
    
    public String alienOrder(String[] words) {
    
        try {
            creategraph(words);
        } catch (Exception e) {
            return "";
        }
    
        return topologicalSort();
    
    }
    
    // based on kahn's algorithm https://en.wikipedia.org/wiki/Topological_sorting
    private String topologicalSort()
    {
        Queue<Node> q = new LinkedList<>();
        for (Map.Entry<Character,Node> entry: maps.entrySet())
        {
            Node value = entry.getValue();
            // Entering the node with no incoming edge;
            if(value.incoming==0)
                q.add(value);
        }
    
        StringBuilder result = new StringBuilder();
    
        while (!q.isEmpty())
        {
            Node top = q.poll();
            result.append(top.val);
    
            for (Node neighbour: top.neigbours)
            {
                // removing the incoming edge
                --neighbour.incoming;
                if(neighbour.incoming==0)
                {
                    q.add(neighbour);
                }
            }
        }
    
        return result.length()!=maps.size()?"":result.toString();
    }
    
    // create the graph
    
    private void creategraph(String[] words) throws Exception
    {
    
        // first create all the nodes with the incoming edge defaults to 0
        for(int i=0;i<words.length;i++)
        {
            for (int j=0;j<words[i].length();j++) {
                char member = words[i].charAt(j);
                if (!maps.containsKey(member)) {
                    maps.put(member, new Node(member));
                }
            }
        }
    
        // then create a relation a directed graph relation. Eg, for wr,wt there will be a Node(r), a Node(t).  Node(t) will be added as neigbour of Node(r). The incoming edge count is also
        // updated for Node(t) as 1
    
        for(int i=0;i<words.length-1;i++)
        {
            String first = words[i];
            String second = words[i+1];
    
            int len = Math.min(first.length(), second.length());
    
            for(int j=0;j<len;j++)
            {
                char left = first.charAt(j);
                char right = second.charAt(j);
                if(left != right)
                {
                    Node leftNode = maps.get(left);
                    
                    Node rightNode = maps.get(right);
                    
                    if(rightNode.neigbours.contains(leftNode))
                        throw new Exception("There is a loop in the graph");
    
                    if(!leftNode.neigbours.contains(rightNode))
                    {
                        leftNode.neigbours.add(rightNode);
                        rightNode.incoming++;
                    }
    
                    break;
    
                }
    
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.