Wrong test case result


  • 4
    J

    input: ["wrtkj","wrt"]
    output: "kjwtr"
    expected: ""

    This is obviously wrong.


  • 1

    For somebody who is not familiar with dictionary like me.
    The reason "wrtkj", "wrt" should return wrong is as following:
    Because "wrtkj" appears before than "wrt"(pay attention to "wrt" is same as prefix of "wrtkj"), this is not allowed lexicographically.
    "wrtkj"
    "wrt"

    For dictionary for language like English.

    "wrt" must appears before "wrtkj", like this:
    "wrt"
    "wrtkj"

    Means your code should check this scenario.

    public String alienOrder(String[] words) {
    Map<Character, Set<Character>> map=new HashMap<Character, Set<Character>>();
    Map<Character, Integer> degree=new HashMap<Character, Integer>();
    String result="";
    if(words==null || words.length==0) return result;
    for(String s: words){
        for(char c: s.toCharArray()){
            degree.put(c,0);
        }
    }
    for(int i=0; i<words.length-1; i++){
        String cur=words[i];
        String next=words[i+1];
        int length=Math.min(cur.length(), next.length());
        for(int j=0; j<length; j++){
            char c1=cur.charAt(j);
            char c2=next.charAt(j);
            if(c1!=c2){
                Set<Character> set=new HashSet<Character>();
                if(map.containsKey(c1)) set=map.get(c1);
                if(!set.contains(c2)){
                    set.add(c2);
                    map.put(c1, set);
                    degree.put(c2, degree.get(c2)+1);
                }
                break;
            } else {
                if(j+1 <= cur.length()-1 && j+1 > next.length()-1) return "";
            }
        }
    }
    Queue<Character> q=new LinkedList<Character>();
    for(char c: degree.keySet()){
        if(degree.get(c)==0) q.add(c);
    }
    while(!q.isEmpty()){
        char c=q.remove();
        result+=c;
        if(map.containsKey(c)){
            for(char c2: map.get(c)){
                degree.put(c2,degree.get(c2)-1);
                if(degree.get(c2)==0) q.add(c2);
            }
        }
    }
    if(result.length()!=degree.size()) return "";
    return result;
    

    }


  • 0

    @hot13399

    Thanks for the explanation! I got your point.

    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.


  • 0

    @markieff yes, I agree, I think they shouldn't make any assumption based on human experience to a alien language. They should explain all the rule for a alien language.


  • 0
    W

    @1337c0d3r I also have this problem, should that be any order of the word?


Log in to reply
 

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