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

• 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!

• 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;
}
``````

}

• 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.

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

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

• @sherry4869 I see!

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