My code is doing something wrong at topSortUtil function. Please help me!!!


  • 0
    S

    I have used the approach of Topological sorting on english alphabets and it seems something wrong in topSortUtil function. Please help if you can catch the mistake:

    
    public class Solution {
        
        int V;
        LinkedList<Integer> adj[];
        
        void createGraph(int V) {
            this.V = V;
            adj = new LinkedList[V];
            for(int i = 0 ; i < V; i++) {
                adj[i] = new LinkedList<Integer>();
            }
        }
        
        void addEdge(int v, int w) {
            adj[v].add(w);
        }
        
        
        public String alienOrder(String[] words) {
            createGraph(26);
            
            for(int i = 0; i < words.length - 1; i++) {
                for(int j = i + 1; j < words.length; j++) {
                    int lengthI = words[i].length();
                    int lengthJ = words[j].length();
                    int min = Math.min(lengthI, lengthJ);
                    for(int k = 0; k < min; k++) {
                        if(words[i].charAt(k) != words[j].charAt(k)) {
                            addEdge(words[i].charAt(k) - 'a', words[j].charAt(k) - 'a');
                        }
                    }
                }
            }
            
            Set<Integer> visited = new HashSet<Integer>();
            Stack<Integer> stack = new Stack<Integer>();
            
            for(int i = 0 ; i < 26; i++) {
                if(visited.contains(i)) {
                    continue;
                }
                topSortUtil(i, visited, stack);
            }
            
            StringBuilder sb = new StringBuilder();
            
            System.out.println(stack.size());
            while(!stack.isEmpty()) {
                int element = stack.pop();
                char c = (char)('a' + element);
                sb.append(c);
            }
            return sb.toString();
        }
        
        void topSortUtil(int i, Set<Integer> visited, Stack<Integer> stack) {
            visited.add(i);
            for(int j = 0 ; j < adj[i].size(); i++) {
                if(visited.contains(adj[i].get(j))) {
                    continue;
                }
                // System.out.println((char)('a' + i) + " " + (char)('a' + adj[i].get(j)));
                System.out.println((char)('a' + i) + " " + adj[i].size());
                topSortUtil(adj[i].get(j), visited, stack);
            }
            //System.out.println((char)('a' + i) + " " + adj[i].size());
            if(adj[i].size() > 0) {
                stack.push(i);
            }
        }
    }
    

Log in to reply
 

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