Confusing Test Case ["wrtkj","wrt"]


  • 0
    Z

    My solution which got AC before can not handle with the new test case ["wrtkj","wrt"]. Can anybody tell me why this is invalid please? Thanks!


  • 0
    Z

    public class Solution {
    boolean cycle = false;
    boolean[] visited = new boolean[26];
    boolean[] onStack = new boolean[26];
    StringBuilder sb = new StringBuilder();

    public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<Character, List<Character>>();
        
        for(int i = 0; i < words.length; i++) {
            for(int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                if(!graph.containsKey(c)) graph.put(c, new ArrayList<Character>());
            }
        }
        
        for(int i = 1; i < words.length; i++) {
            int len = Math.min(words[i - 1].length(), words[i].length());
            for(int j = 0; j < len; j++) {
                char a = words[i - 1].charAt(j);
                char b = words[i].charAt(j);
                
                if(a != b) {
                    graph.get(a).add(b);
                    break;
                }
            }
        }
        
        Set<Character> verxSet = new HashSet(graph.keySet());
        
        for(Character c : verxSet) {
            if(!visited[c - 'a'] && !cycle)
                dfs(graph, c);
        }
        
        if(cycle) return "";
        
        return sb.toString();
    }
    
    public void dfs(Map<Character, List<Character>> graph, Character cur) {
        visited[cur - 'a'] = true;
        onStack[cur - 'a'] = true;
        
        List<Character> list = graph.get(cur);
        for(Character next : list) {
            if(onStack[next - 'a']) {
                cycle = true;
                return;
            } else if(!visited[next - 'a'] && !cycle) {
                dfs(graph, next);
            }
        }
        
        sb.insert(0, cur);
        onStack[cur - 'a'] = false;
    }
    

    }


  • 3
    J

    It's invalid because wrtkj should never appear before wrt in dictionary order. Basically if word A is the prefix of word B, then a proper dictionary would put A before B.


  • 0
    S

    While you are making graph, you are able to check if it is invalid.


  • 0
    Z

    @jenskirgel Thanks, man! This was a corner case that I did not considered before.


  • 0
    Z

    @sherry4869 I see!


Log in to reply
 

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