For ["zy","zx"], shouldn't the output be an empty string ?


  • 0
    A

    When the input is ["zy","zx"], we can only establish that 'y' comes before 'x', but we don't know what the priority of 'z' is with respect to 'y' and 'x'. So shouldn't the output be an empty string "" ? The Judge says the output is "zyx" and I fail to see how that's the case.


  • 0
    A

    @ahmadka
    In this scenario there are many valid solutions. We don't know any relation between z&a so either orders are correct. The problem statements mentioned to print any solution if more than one exist.


  • 0

    In case of multiple possible solutions, the problem stated that any valid solution is fine. So for this particular case, any one of "zyx", "yzx", "yxz" will be considered as a valid solution.

    By the way, inspired by your question, it will be an even more interesting problem to think about how an alien dictionary can uniquely define an alphabet (i.e., no "free" letters)? I saw there is another problem in OJ "Sequence Reconstruction" which might give a clue.


Log in to reply
 

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