Wrong test case: for test case ["wrtkj","wrt"], we are doing this based on "Alien" dictionary.


  • 25

    Let's see these two test cases:

    for test case ["xz","xy"], the expected answer is xzy. It means that we don't need to care about the position of the letters without dependency, like x. The answer can be like xzy, zyx, zxy. As long as z is in front of y.

    But for test case ["wrtkj","wrt"], the expected answer is "". Interesting..
    according to test case ["xz","xy"], the result of ["wrtkj","wrt"] can be any order Coz there is no dependency of the letters.

    Some people says that because "wrt" is the prefix of "wrtkj", it should appear first.

    But I think this question is called "Alien Dictionary" and there are no specific rules for the situation like "wrtkj", "wrt".
    I may say that according to this "Alien" lexicography, "a" should appear after "ab", and "ab" should appear after "aba", that's totally possible, Coz it's allowed "Alien" lexicographically.

    I think if they want us to solve the problem based on the rule you mentioned, they should make it clear.

    If I am wrong about this, please do let me know, thanks guys.


  • 0
    S

    I had same understanding as you at the beginning.
    I think ["wrtkj","wrt"] should have no answer instead of any answer.

    The "" should come first before any letter. So, "wrt" should come before "wrtkj". This case give a wrong order, should should return "" which means no answer.


  • 0

    @sjy Why "The "" should come first before any letter"?


  • 0
    S

    @markieff how you sort these English words. "abc", "abcd", "ab"


  • 0

    @sjy I can do "ab" "abc" "abcd" based on English Dictionary,
    OR, I can do "abcd" "abc" "ab" based on some Alien Dictionary,
    even "abcd" "ab" "abc"


  • 0
    S

    @markieff I agree. Actually.
    But that's the not the logic in this question.


  • 0

    This prefix test case does fail my code before I fixed it.
    I agree that technically, if there is a prefix pair [str1,str2] showing up in alien dictionary, then it actually defines an order between " " and the character which is just beyond the length of the shorter string. Then " " should come into the final "alien alphabet" just like any other "normal" characters. For this particular case, it just defines letter k comes before" " in "alien alphabet" and that's all. And the final alphabet should also contain a" " in the appropriate location.

    However, I guess for" ", even aliens agree with human beings' dictionary by convention :-)


  • 0
    W

    encountered the same question.
    @administrators


  • 0
    J

    @sjy

    There is another test case as [ "z", "z"] , expect result is "z"
    Are you able to explain?


  • 0

    There is another test case as [ "z", "z"] , expect result is "z"
    Are you able to explain?

    Note that for all letters shown in Alien Dictionary, actually they can be split into two categories:

    1. free letters: no order defined based on the given dictionary;
    2. ordered letters: there is a relative order implied from the dictionary with respect to other ordered letters.

    Dictionary ["z", "z"] has only one letter 'z' which is a free letter, so it is simply included in the alien alphabet.


  • 0
    S

    Same question..
    Given input "wrtkj", "wrt"
    If I output: "wtr", get expected: ""
    while if I output: "", get expected:"jkrtw"


  • 0

    @sweetteaoh

    Same question..
    Given input "wrtkj", "wrt"
    If I output: "wtr", get expected: ""
    while if I output: "", get expected:"jkrtw"

    Not quite get what you meant by "If I output".

    There is actually a hidden assumption in this problem is that empty space always comes before any letter (while some coders do not like it and I think the problem itself should probably clarify it). So input ["wrtkj", "wrt"] violate this "rule" and expected answer is simple "".

    Assuming we ignore this rule, i.e., "" is treated like a regular letter just like others, then the only thing we can derive from input ["wrtkj", "wrt"] is that 'k' comes before "" and that's it because 'k' vs "" is the first position where these two words differ. So any alien alphabet consisting letters w, r, t, k, j plus"" with 'k' before "" should be a valid answer. However, it is weird to put "" in any alphabet and I guess that's why this OJ problem silently hard coded a fixed order for "" vs any other letters because this is not the major point for this question.


  • 2
    J

    @zzg_zzm
    below is what I got, why? I can't understand why we need to think about ""
    ["wrt","wrtkj"] ==> "jkrtw"
    ["wrtkj","wrt"] ==> ""
    Btw ["z","z"] ==> "z"
    to be frankly, i would like the owner of leetcode can remove such kind of ambiguous
    testcases although we may not need to consider those things during the real interview
    such kind of so called corner case can't evaluate your coding skill/algorithm skill/computer science fundamentals...

    @administrators @leetcode1337(?)


  • 0

    @zzg_zzm
    below is what I got, why? I can't understand why we need to think about ""
    ["wrt","wrtkj"] ==> "jkrtw"

    The first word is a prefix of second, which is universally true in alien dictionary, so any alphabet of those five letters is a valid answer. To compare after 3 letters, we already exhausted the short one, so we have to compare empty char '' with 'k', where '' always comes before 'k' anyway by the hidden assumption. No we couldn't derive any order at all from this dictionary.

    ["wrtkj","wrt"] ==> ""

    The second is a prefix of the first, which always violates the '' comes before any letter rule, so no alphabet.

    Btw ["z","z"] ==> "z"

    All words in dictionary are identical, so no order is indicated at all. So any alphabet with 'z' (which is just 'z') is a valid answer.

    to be frankly, i would like the owner of leetcode can remove such kind of ambiguous
    testcases although we may not need to consider those things during the real interview
    such kind of so called corner case can't evaluate your coding skill/algorithm skill/computer science fundamentals...

    I totally agree with your points here. In real interview, you would have opportunities to clarify with the interviewer. I've also seen other OJ problems with undefined/non-intuitive corner case answers. I would just attempt to submit my solution to fail and try to "reverse engineer" what is OJ's expected logic. Of course, as you mentioned, OJ should have at least modified the problem statement for better clarification.

    @administrators @leetcode1337(?)


  • 1

    agree, dont make things too complex since they r useless for real interview
    @administrators @1337c0d3r @contributors


  • 2

    @administrators @1337c0d3r @contributors
    Agreed! The key part of this question is use topological sorting to verify cycle of dependencies.
    Checking the lexicographical order of "" just blurs the focus!!


  • 0
    C

    Well it actually makes sense.
    the key thing is that "wrtkj" is lexicographically larger than "wrt", but it is placed before "wrt", which results in a contradiction. so there is no answer


  • 0

    @cgxy1995 please read what I wrote please, I have explained this.


  • 0
    C

    @markieff I read it. But I think my interpretation makes more sense. by lexicographical order, "wrt" should just go before "wrtkj". A wrong input results in no answer.


  • 0

    @cgxy1995 I got your point. But I think if we define a new dictionary, both lexicographical order and letter order should be included. Not just the order of all the letters.


Log in to reply
 

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