Code gets correct answer on IDE for sample input, but does not work correctly on the online judge, can anyone see why?


  • 1
    T
    public class Solution {
      public String alienOrder(String[] words) {
            int min;
            String earlier, later;
            char earlierChar, laterChar;
            List tempSet;
            Map<Character, List<Character> > characterDependecy = new HashMap<>();
            for(int ii = 0; ii < words.length - 1; ii++){
                earlier = words[ii];
                later = words[ii + 1];
                min = Math.min(earlier.length(), later.length());
                for(int jj = 0; jj < min; jj++){
                    earlierChar = earlier.charAt(jj);
                    laterChar = later.charAt(jj);
                    if(earlierChar != laterChar){
                        if(!characterDependecy.containsKey(laterChar))
                            characterDependecy.put(laterChar, new ArrayList<Character>());
                        tempSet = characterDependecy.get(laterChar);
                        tempSet.add(earlierChar);
                        break;
                    }
                }
            }
    
            return topologicalSort(characterDependecy);
        }
    
        private String topologicalSort(Map<Character, List<Character> > characterDependecy){
            StringBuilder result = new StringBuilder();
            Set<Character> visited = new HashSet<>();
            for(Character each : characterDependecy.keySet()){
                if(!visited.contains(each))
                    topologicalSortUtil(characterDependecy, each, result, visited);
            }
            return result.toString();
        }
    
        private void topologicalSortUtil(Map<Character, List<Character> > characterDependecy, Character each, StringBuilder result, Set<Character> visited){
            List <Character> dependencies = characterDependecy.get(each);
            if(!visited.contains(each) && dependencies != null) {
                for (Character chars : dependencies) {
                    visited.add(each);
                    topologicalSortUtil(characterDependecy, chars, result, visited);
                }
            }
            result.append(each);
        }
    }

  • 0
    Y

    Have the same issue. When the input is ["ab", "abc"], the OJ return "abd", but my local IDE return "abc".

    class Solution {
    public:
    string alienOrder(vector<string>& words) {
        map<char, set<char>> neighbor;
        map<char, set<char>> inChar;
        //construct the graph
        for(int i = 0; i < words.size()-1; i++){
            string word1 = words[i];
            string word2 = words[i+1];
            int p = 0;
            while(p<word1.size() && p<word2.size() && word1[p] == word2[p]){
                neighbor[word1[p]];
                inChar[word1[p]];
                p++;}
            if(p==word1.size() || p==word2.size()){
                if(p==word1.size() && p!=word2.size()){
                    neighbor[word2[p]];
                    inChar[word2[p]];
                }
                continue;
            }
            neighbor[word1[p]].insert(word2[p]);
            inChar[word2[p]].insert(word1[p]);
            inChar[word1[p]];
            
        }
        //init the queue
        queue<char> queue;
        for(auto p : inChar){
            if(p.second.size() == 0)
                queue.push(p.first);
        }
        //do the topological sort
        string rlt = "";
        while(!queue.empty()){
            char cur = queue.front();
            queue.pop();
            rlt += cur;
            for(auto c : neighbor[cur]){
                inChar[c].erase(cur);
                if(inChar[c].size() == 0)
                    queue.push(c);
            }
        }
    
        //determine if valid
        bool valid = true;
        for(auto p : inChar){
            if(p.second.size() != 0){
                valid = false;
                break;
            }
        }
        //return
        return valid ? rlt : "";
    }
    

    };


  • 0
    T

    Try using Java 1.8 locally, not sure what the actual problem is but it seemed to help replicate my issue locally.


Log in to reply
 

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