Missing Test Case


  • 0
    D

    Input: ["a","b","ca","cc"]

    Accepted Incorrect Solution that will return empty string rather than "abc" is attached at the end.
    Please add the above test case.

    The problem is that the pathDown is not recovered. It may cause confuse code of cycle detected depending on visit order.

    This is similar to, but different from, this post:
    https://leetcode.com/discuss/69862/missing-test-case
    Unfortunately different code may choke on different use cases depending on access order. (e.g i'm using array and start visiting in alphabetical order)

    public class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) return "";
        
        // Build up adjacency list
        Set<Character>[] lowOrderSets = new Set[26];
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String word2 = "";
            // If word2 uses word as prefix, word2 is no shorter than word.
            // I.e. if word2 is shorter than word there must be some different letters
            boolean orderDetermined = false;
            if (i < words.length - 1) {
                word2 = words[i + 1];;
            } else { // Last word, just make sure the chars/vertices are recorded
                orderDetermined = true;
            }
            for (int j = 0; j < word.length(); j++) {
                char cur = word.charAt(j);
                Set<Character> lowOrderSet = lowOrderSets[cur-'a'];
                if (lowOrderSet == null) {
                    lowOrderSet= new HashSet<>();
                    lowOrderSets[cur-'a'] = lowOrderSet;
                }
                if (!orderDetermined) {
                    if (j == word2.length()) {
                        // Invalid order found: word2 is shorter than word
                        // but word is a prefix of word2. E.g. abc, a
                        return "";
                    }
                    if (cur != word2.charAt(j)) {
                        lowOrderSet.add(word2.charAt(j));
                        orderDetermined = true;
                    }
                }
            }
        }
        
        // Topological sort into stack using DFS 
        Deque<Character> stack = new ArrayDeque<>();
        Set<Character> visited = new HashSet<Character>(40);
        try {
            for (int i = 0; i < 26; i++) {
                char c = (char) ('a' + i);
                if (lowOrderSets[i] != null) {
                    visit(c, lowOrderSets, stack, new HashSet<Character>(), visited);
                }
            }
        } catch (IllegalStateException ise) { // invalid input detected
            return "";
        }
        
        // Print out result
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
    
    private void visit(char c, Set<Character>[] sets, Deque<Character> stack, 
        Set<Character> pathDown, Set<Character> visited) {
        if (!visited.contains(c)) {
            if (sets[c-'a'] == null) { // It's possible to be empty though
                throw new RuntimeException("Code error, vertex has empty adjacency list!");
            }
            pathDown.add(c);
            for (Character nextC : sets[c-'a']) {
                if (pathDown.contains(nextC)) {
                    // Cycle detected; can be a checked exception
                    throw new IllegalStateException("Invalid input with cycles.");
                }
                visit(nextC, sets, stack, pathDown, visited);
            }
            visited.add(c);
            stack.push(c);
        }
    }
    

    }


  • 0

    Thanks! I have added your test case.


Log in to reply
 

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