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.
典型的Topological sort
注意以下个例:
1. 有环
2. ["z", "z"]
3. ["wz", "w"]
class Solution { private boolean circle = false; public String alienOrder(String[] words) { Map<Character, Set<Character>> map = getGraph(words); Map<Character, Integer> visited = new HashMap<>(); StringBuilder rt = new StringBuilder(); for (Character c : map.keySet()) { dfs(map, c, visited, rt); } if (circle) return ""; return rt.reverse().toString(); } private void dfs(Map<Character, Set<Character>> map, char cur, Map<Character, Integer> visited, StringBuilder sb) { if (visited.containsKey(cur) && visited.get(cur) == 1) { circle = true; return; } if (visited.containsKey(cur) && visited.get(cur) == -1) return; visited.put(cur, 1); for (Character c : map.get(cur)) { dfs(map, c, visited, sb); } visited.put(cur, -1); sb.append(cur); } private Map<Character, Set<Character>> getGraph(String[] words) { Map<Character, Set<Character>> map = new HashMap<>(); for (String w : words) { for (int i = 0; i < w.length(); i++) { map.put(w.charAt(i), new HashSet<>()); } } for (int i = 1; i < words.length; i++) { for (int j = 0; j < words[i].length() && j < words[i - 1].length(); j++) { char c1 = words[i - 1].charAt(j); char c2 = words[i].charAt(j); if (c1 == c2) continue; map.get(c1).add(c2); break; } } return map; } }
ToDo
2.用BFS再写一遍
No comments:
Post a Comment