Incorrect Test Case - 269. Alien Dictionary

LeetCode Username

spitchai

Problem number, title, and link

269 Alien Dictionary](https://leetcode.com/problems/alien-dictionary/

Category of the bug

[ ] Incorrect test Case (Output of test case is incorrect as per the problem statement)

Description of the bug

In this problem if the adj list is empty, i.e no relations can be extracted from the input. the output should be zero. "". example: ["wrt","wrtkj"]

There cannot be any relation that can be established. hence the output should be null string. but the expected output is "jkrtw". i know why is this expected, that is because it is a coding bug. since the adjacency list is empty all the in-degree is zero. so when we do a kahn's algorithm on it, it is going to go through the queue and add all the char in the words.

Language used for code

C++

Code used for Submit/Run operation

class Solution {
public:
    void bld_adj(string& a, string& b, map<char, set<char>>& adj) {
        int sz = min(a.size(), b.size()), i = 0;

        while ((i < sz) && (a[i] == b[i]))
            i++;
        if (i < sz)
            adj[a[i]].insert(b[i]);
    }
string alienOrder(vector<string>& words) {
      map<char, set<char>> adj;
      set<char> nlist;
      map<char, int> deg;
      queue<char> q;
      string rt;

      for (auto word: words) {
        for (auto c : word) nlist.insert(c);
      }

      if (nlist.size() == 1) {
        for (auto c : nlist) rt.push_back(c);
        return rt;
      } else if (!nlist.size()) return "";

      for (int i = 1; i < words.size(); i++) {
        bld_adj(words[i - 1], words[i], adj);
      }
      if (!adj.size()) return "";

      for (auto c : nlist) deg[c] = 0;

      for (auto [n, nbrs] : adj) {
        for (auto nbr: nbrs) deg[nbr]++;
      }

      for (auto [k,v] : deg) {
        if (v == 0) q.push(k);
      }

      while (q.size()) {
        auto node = q.front();
        q.pop();

        rt.push_back(node);

        auto nbrs = adj[node];
        for (auto nbr : nbrs) {
          deg[nbr]--;
          if (deg[nbr] == 0) {
            q.push(nbr);
          }
        }
      }

      if (rt.size() == nlist.size()) return rt;
      return "";
    }
};

Expected behavior

expected behaviour should be ""

Screenshots

Additional context

Dear user,

Thank you for submitting your code to our platform. After a thorough evaluation, we regret to inform you that your code did not produce the expected results. Our code judge is functioning correctly, and we have verified the correctness of our evaluation process.

We kindly suggest that you review your code carefully and ensure it adheres to the problem requirements and constraints. It may be beneficial to double-check your logic, algorithm implementation, and any potential errors or corner cases that could affect the code's performance.

Additionally, we encourage you to explore our discussion board, where you can seek assistance from the community. Many experienced users and experts are available to help troubleshoot issues, provide insights, and offer guidance on improving your code.

We believe that by reviewing your code and actively engaging with the community, you will have a better chance of identifying and resolving the discrepancies. Remember, learning from such experiences and iterating on your code is an essential part of the programming journey.

We appreciate your understanding and encourage you to continue learning and improving your coding skills.

Should you have any further questions or need additional support, please don't hesitate to reach out to us.

Best regards,

The LeetCode Team

LeetCode-Feedback / LeetCode-Feedback