There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input: [ "z", "x", "z" ] Output:""
Explanation: The order is invalid, so return""
.
Note:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
class Solution { Map<Character, Set<Character>> links = new HashMap<>(); public String alienOrder(String[] words) { int i = 0; boolean cont = true; while(cont) { String prefix0 = ""; char pChar = '.'; cont = false; for(String w : words) { if(w.length() < i) continue; //"er**", if i = 3 skip String prefix = w.substring(0, i); if(w.length() >= i+1) { cont = true; char c = w.charAt(i); if(!links.containsKey(c)) links.put(c, new HashSet<>()); if(prefix.equals(prefix0) && pChar!='.' && pChar != c) links.get(pChar).add(c); pChar = c; }else{//w.length() == i // for case "abc","ab" if(prefix.equals(prefix0) && pChar != '.') return ""; } prefix0 = prefix; } i++; } Set<Character> visited = new HashSet<Character>(); Set<Character> path = new HashSet<Character>(); List<Character> seq = new ArrayList<Character>(); for(Map.Entry e : links.entrySet()) { char node = (char) e.getKey(); if(!visited.contains(node)) { path.add(node); if(hasCycle(visited, path, seq, node)) return ""; path.remove(node); } } Collections.reverse(seq); return seq.stream().map(Object::toString).collect(Collectors.joining("")); } boolean hasCycle(Set<Character> visited, Set<Character> path, List<Character> seq, char c) { visited.add(c); for(char next : links.get(c)) { if(path.contains(next)) return true; if(visited.contains(next)) continue; path.add(next); if(links.containsKey(next) && hasCycle(visited, path, seq, next)) return true; path.remove(next); } seq.add(c); return false; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | class Solution { Map<Character, Set<Character>> links = new HashMap<>(); public String alienOrder(String[] words) { int len = words.length; int j = 0; boolean cont = true; while(cont){ String prefix0 = ""; char ch0 = '.'; cont = false; for(int i=0; i<len; ++i){ String w = words[i]; String prefix = words[i].substring(0, Math.min(w.length(), j)); if(j>=w.length()){ if(prefix.equals(prefix0) && ch0!='.') return ""; prefix0 = prefix; ch0 = '.'; }else{ cont = true; char ch = words[i].charAt(j); if(!links.containsKey(ch)) links.put(ch, new HashSet<>()); if(prefix.equals(prefix0) && ch0!=ch && ch0!='.'){ links.get(ch0).add(ch); } prefix0 = prefix; ch0 = ch; } } j++; } Set<Character> path = new HashSet<>(); Set<Character> visited = new HashSet<>(); List<Character> list = new ArrayList<>(); for(char node : links.keySet()){ if(visited.contains(node)) continue; path.add(node); if(hasCycle(path, visited, list, node)) return ""; path.remove(node); } String ret = ""; for(char c : list) ret += c; return ret; } boolean hasCycle(Set<Character> path, Set<Character> visited, List<Character> list, char node){ visited.add(node); for(char nxt : links.get(node)){ if(path.contains(nxt)) return true; if(visited.contains(nxt)) continue; path.add(nxt); if(hasCycle(path, visited, list, nxt)) return true; path.remove(nxt); } list.add(0, node); return false; } } |
No comments:
Post a Comment