Why my union-find solution always get "Special judge: No expected output available."


  • 0

    Why my union-find solution always get "Special judge: No expected output available."? The output is "" (empty string) on my local machine. Code is below -

        public String alienOrder(String[] words) {
        if (words == null || words.length <= 1) return "";
        List<Character> list = new LinkedList<>();
        char[] union = new char[26];
        for (int wi = 1; wi < words.length; wi++) {
            char[] chars1 = words[wi - 1].toCharArray();
            char[] chars2 = words[wi].toCharArray();
    
            for (int ci = 0; ci < chars1.length; ci++) {
                char c = chars1[ci];
                if (union[c - 'a'] == 0) union[c - 'a'] = c; // char root itself
                if (!list.contains(c)) list.add(c);
            }
    
            for (int ci = 0; ci < chars2.length; ci++) {
                char c = chars2[ci];
                if (union[c - 'a'] == 0) union[c - 'a'] = c; // char root itself
                if (!list.contains(c)) list.add(c);
            }
    
            int minLen = Math.min(chars1.length, chars2.length);
            for (int ci = 0; ci < minLen; ci++) {
                char c1 = chars1[ci], c2 = chars2[ci];
                if (c1 != c2) {
                    char r1 = find(union, c1), r2 = find(union, c2);
                    if (r1 != r2) connect(union, r1, r2);
    
                    int c1i = list.indexOf(c1);
                    int c2i = list.indexOf(c2);
                    if (c1i > c2i) {
                        list.remove(c1i);
                        list.add(c2i, c1);
                    }
                    break;
                }
            }
        }
    
        int rootCounter = 0;
        for (int i = 0; i < 26; i++) {
            if (union[i] == 0) continue;
            if (union[i] == (char) ('a' + i)) rootCounter++;
        }
    
        if (rootCounter > 1) return "";
        StringBuilder builder = new StringBuilder();
        for (Character c : list) builder.append(c);
        return builder.toString();
    }
    
    public void connect(char[] union, char c1, char c2) {
        union[c2 - 'a'] = c1;
    }
    
    public char find(char[] union, char c) {
        while (union[c - 'a'] != c) c = union[c - 'a'];
        return c;
    }

Log in to reply
 

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