Is the test case wrong? Why z < x and why y < z?


  • 0
    C

    I failed a test case which is
    input: ["zy","zx"]
    expect: "yzx"
    If only words are sorted in lexicographically order, how can we say z < x and y < z?
    Could someone help me understand this? Thanks in advance!


  • 0
    H

    Same question from me.


  • 0
    H

    Here is what I found out. My code checks how many chars with degree 0. If there are more than one chars with degree 0, that means there is no answer. There is no order if two chars have degree 0 at the same time.

    After I removed this check, my code passed the test. But that was wrong. We should check that.


  • 0
    H

    The following is my code, which passed the test. But the correct code should include the commented two lines, which will not pass the test.

    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            unordered_map<char, unordered_set<char>> charMap;
            unordered_map<char, int> degree;
            
            for (auto &w : words) {
                for (auto c : w) {
                    if (degree.count(c) == 0)
                        degree[c] = 0;
                }
            }
            
            int count = degree.size();
            
            for (int i = 1; i < words.size(); ++i) {
                auto & prev = words[i-1];
                auto & current = words[i];
                for (int j = 0; j < min(prev.size(), current.size()); ++j) {
                    if (prev[j] != current[j]) {
                        if (charMap[prev[j]].count(current[j]) == 0) {
                            charMap[prev[j]].insert(current[j]);
                            degree[current[j]]++;
                        }
                        break; 
                    }
                }
            }
    
            queue<char> tasks;
            string result;
            result.reserve(count);
            for (auto &onePair : degree) {
                if (onePair.second == 0) {
                    tasks.push(onePair.first);
                }
            }
    
            while (!tasks.empty()) {
                // The judge is wrong. Must check this!
                // The correct code should uncomment the following two lines. 
                /*
                if (tasks.size() != 1) {
                    return string("");
                }
                */
                    
                char c = tasks.front();
                tasks.pop();
                result.push_back(c);
                
                degree.erase(c); 
                
                for (auto c2 : charMap[c]) {
                    degree[c2]--;
                    if (degree[c2] == 0)
                        tasks.push(c2);
                }
            }
            
            if (result.size() == count)
                return result;
            else
                return string();
        }
    };
    

  • 0
    C

    @hq888 I think the problem is the test only allow one valid order of letters while the description says "multiple valid order of letters". So after you remove the check, it generate one valid order of letters, which is the same as the test expected, so you pass the tests. When you have the check, you should be able to return any one of the multiple possible valid order of letters, however the test system is not intelligent enough, so if you pick the one that is not their expected, you will fail the test.


  • 0
    F
    This post is deleted!

Log in to reply
 

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