看到discuss里面一个时间空间都效率比较高的方法，但是有点hard coded，没那么直观
因为确定只有26个字母，所以可以直接开一个char[26]
Let's build a graph and perform a DFS. The following states made things easier.
visited[i] = -1. Not even exist.visited[i] = 0. Exist. Non-visited.visited[i] = 1. Visiting.visited[i] = 2. Visited.
五刷 07/2022
Version #1 DFS Topological Sort
DFS Topological Sort的难点就是不仅需要一个全局的visited set还需要一个path set来判断有没有环
Time O(C) - total length of all words
Space O(1)
Runtime: 5 ms, faster than 83.85% of Java online submissions for Alien Dictionary.
Memory Usage: 43.3 MB, less than 22.79% of Java online submissions for Alien Dictionary.
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
putAllChars(words[0], graph);
for (int i = 1; i < words.length; i++) {
putAllChars(words[i], graph);
if (!addEdge(words[i - 1], words[i], graph)) {
return "";
}
}
StringBuilder sb = new StringBuilder();
Set<Character> visited = new HashSet<>();
for (Character c : graph.keySet()) {
if (!dfs(c, graph, sb, visited, new HashSet<>())) {
return "";
}
}
return sb.reverse().toString();
}
private boolean dfs(Character c, Map<Character, Set<Character>> graph, StringBuilder sb, Set<Character> visited, Set<Character> path) {
if (visited.contains(c)) {
return true;
}
path.add(c);
for (Character next : graph.getOrDefault(c, new HashSet<>())) {
if (path.contains(next)) {
return false;
}
if (!dfs(next, graph, sb, visited, path)) {
return false;
}
}
path.remove(c);
visited.add(c);
sb.append(c);
return true;
}
private void putAllChars(String word, Map<Character, Set<Character>> graph) {
for (int i = 0; i < word.length(); i++) {
graph.putIfAbsent(word.charAt(i), new HashSet<>());
}
}
private boolean addEdge(String smaller, String larger, Map<Character, Set<Character>> graph) {
for (int i = 0; i < Math.min(smaller.length(), larger.length()); i++) {
char a = smaller.charAt(i);
char b = larger.charAt(i);
if (a == b) {
continue;
}
graph.get(a).add(b);
return true;
}
return smaller.length() <= larger.length();
}
}
Version #2 BFS + indegree 四刷 05/2022
出现了前面出现的bug就是要提前把每个word里面所有的characters都加到map里面
另外一个就是有环的问题，这里BFS就不如DFS直观
Runtime: 10 ms, faster than 19.83% of Java online submissions for Alien Dictionary.
Memory Usage: 43.1 MB, less than 26.43% of Java online submissions for Alien Dictionary.
class Solution {
public String alienOrder(String[] words) {
// From "wrt" < "wrf" we got "t" < "f"
// Then we can construct part of the graph t -> f
// We can build to whole graph with this rule and do a topological sort
Map<Character, Set<Character>> map = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
try {
buildGraph(words, map, indegree);
} catch (IllegalArgumentException e) {
return "";
}
Queue<Character> que = new ArrayDeque<>();
for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
if (entry.getValue() == 0) {
que.offer(entry.getKey());
}
}
StringBuilder sb = new StringBuilder();
while (!que.isEmpty()) {
Character curr = que.poll();
sb.append(curr);
for (Character next : map.getOrDefault(curr, new HashSet<>())) {
int nId = indegree.get(next) - 1;
if (nId == 0) {
que.offer(next);
}
indegree.put(next, nId);
}
}
if (sb.length() != map.keySet().size()) {
return "";
}
return sb.toString();
}
private void buildGraph(String[] words, Map<Character, Set<Character>> map, Map<Character, Integer> indegree) throws IllegalArgumentException {
String prev = null;
for (String curr : words) {
for (char c : curr.toCharArray()) {
map.putIfAbsent(c, new HashSet<>());
indegree.putIfAbsent(c, 0);
}
if (prev == null) {
prev = curr;
continue;
}
int i = 0;
int prevLen = prev.length();
int currLen = curr.length();
Character from = null, to = null;
for (i = 0; i < Math.min(prevLen, currLen); i++) {
if (prev.charAt(i) != curr.charAt(i)) {
from = prev.charAt(i);
to = curr.charAt(i);
break;
}
}
if (i == Math.min(prevLen, currLen)) {
if (prevLen > currLen) {
throw new IllegalArgumentException();
}
continue;
}
if (!map.get(from).contains(to)) {
map.get(from).add(to);
int id = indegree.getOrDefault(to, 0);
indegree.put(to, id + 1);
}
prev = curr;
}
}
}
Version #1 DFS
三刷
记住dfs做topological sort的最核心的一点就是
only add nodes whose children are fully explored to stack
依然卡在了忘了把所有出现的char但是不具备决定关系的char加到map里面
2.33 %
class Solution {
public String alienOrder(String[] words) {
// dfs topological sort, only add nodes whose children are fully explored to stack
if (words == null || words.length == 0) return "";
Map<Character, Set<Character>> map = buildGraph(words);
Deque<Character> stack = new ArrayDeque<>();
Set<Character> visited = new HashSet<>();
for (char c : map.keySet()) {
if (!visited.contains(c) && !dfs(c, map, stack, visited, new HashSet<>())) { // has cycle
return "";
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
private boolean dfs(char c, Map<Character, Set<Character>> map, Deque<Character> stack,
Set<Character> visited, Set<Character> path) {
if (path.contains(c)) { // see a loop
return false;
}
if (visited.contains(c)) {
return true;
}
path.add(c);
visited.add(c);
Set<Character> children = map.get(c);
for (Character next : children) {
if (!dfs(next, map, stack, visited, path)) {
return false;
}
}
path.remove(c);
stack.push(c);
return true;
}
private Map<Character, Set<Character>> buildGraph(String[] words) {
Map<Character, Set<Character>> map = new HashMap<>();
for (int i = 1; i < words.length; i++) {
String prev = words[i - 1];
String curr = words[i];
for (int j = 0; j < Math.min(prev.length(), curr.length()); j++) {
char p = prev.charAt(j);
char c = curr.charAt(j);
if (p != c) {
map.computeIfAbsent(p, set -> new HashSet<>()).add(c);
break;
}
}
}
for (String word : words) {
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
map.putIfAbsent(c, new HashSet<>());
}
}
return map;
}
}
二刷
依然是卡在不能决定顺序的所有characters也要输出 这个点上
这一次上来直接就写了hashmap
依然是把words里面所有的char都先加到hashmap 的key里面
73.56 %
class Solution {
public String alienOrder(String[] words) {
if (words == null || words.length == 0) return "";
Map<Character, List<Character>> graph = buildGraph(words);
if (graph == null) return ""; //invalid graph
List<Character> result = new ArrayList<>();
Set<Character> path = new HashSet<>();
Set<Character> visited = new HashSet<>();
for (Character curr : graph.keySet()) {
if (!dfs(curr, graph, path, visited, result)) return "";
}
StringBuilder sb = new StringBuilder();
for (int i = result.size() - 1; i >= 0; i--) {
sb.append(result.get(i));
}
return sb.toString();
}
//if there's a cycle, return false
private boolean dfs(Character curr, Map<Character, List<Character>> graph, Set<Character> path, Set<Character> visited, List<Character> result) {
if (path.contains(curr)) return false; // there's a cycle
if (visited.contains(curr)) return true; // the area has already been explored
List<Character> neighbors = graph.get(curr);
if (neighbors != null) {
path.add(curr);
for (Character neighbor : neighbors) {
if (!dfs(neighbor, graph, path, visited, result)) {
path.remove(curr);
return false;
}
}
path.remove(curr);
}
// neighbors == null, curr is the last node
visited.add(curr);
result.add(curr);
return true;
}
private Map<Character, List<Character>> buildGraph(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
for (char c : words[0].toCharArray()) {
graph.put(c, new ArrayList<>());
}
for (int i = 0; i < words.length - 1; i++) {
for (char c : words[i + 1].toCharArray()) {
if (!graph.containsKey(c)) graph.put(c, new ArrayList<Character>());
}
// relation[0] current char, relation[1] next char
char[] relation = getNeighbor(words[i], words[i + 1]);
//You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
if (relation == null) return null;
if (relation.length == 0) continue;
graph.get(relation[0]).add(relation[1]);
}
return graph;
}
private char[] getNeighbor(String curr, String next) {
int index = 0;
while (index < curr.length() && index < next.length()) {
char c1 = curr.charAt(index);
char c2 = next.charAt(index);
if (c1 != c2) return new char[]{c1, c2};
else index++;
}
//next is shorter than curr, next is a prefix of curr
if (index < curr.length()) {
return null;
} else { // curr is a prefix of next || curr.equals(next)
return new char[0];
}
}
}
一刷
感觉自己DFS写的不好所以用DFS写一下
对于graph表示的方法有问题
一开始写了一个boolean[26][26]后来发现不符合题意
因为如果key是26默认所有characters都出现了，然而并不是这样，只有看到的character才算数
所以用hashmap比较直观
有一个很大的bug就是在buildGraph的时候要把所有characters加入到hashmap里面
因为当两个string有char不一样的时候就会break，所以直接后面的characters都看不见了
一个比较无脑的方法就是先把所有words都看一下，把所有的char都作为key提前加入到hashmap里面，就不会有遗漏了
对topological sorting的定义还是理解的不到位，觉得如果只有一个输入词的话没有顺序可以输出，然而对于topo sorting来说，不能决定的顺序就是可以以任意顺序输出
所以hashmap需要包含所有的word里面的characters
55.16 %
public class Solution {
public String alienOrder(String[] words) {
if (words == null) return "";
Map<Character, Set<Character>> graph = new HashMap<>();
for (String word : words) {
for (char ch : word.toCharArray()) {
if (!graph.containsKey(ch)) graph.put(ch, new HashSet<>());
}
}
if (!buildGraph(words, graph)) return "";
for (Character c : graph.keySet()) {
}
//TODO
Stack<Character> order = new Stack<>();
Boolean[] hasOrder = new Boolean[26];
Set<Character> visiting = new HashSet<>();
for (Character c : graph.keySet()) {
if (!getOrder(c, graph, visiting, hasOrder, order)) return "";
}
StringBuilder sb = new StringBuilder();
while (!order.isEmpty()) {
sb.append(order.pop());
}
return sb.toString();
}
private boolean getOrder(Character c, Map<Character, Set<Character>> graph, Set<Character> visiting, Boolean[] hasOrder, Stack<Character> order) {
if (visiting.contains(c)) return false;
if (hasOrder[c - 'a'] != null) return hasOrder[c - 'a'];
if (!graph.containsKey(c)) {
hasOrder[c - 'a'] = true;
order.push(c);
return true;
}
visiting.add(c);
boolean currHasOrder = true;
for (Character neighbor : graph.get(c)) {
if (!getOrder(neighbor, graph, visiting, hasOrder, order)) {
currHasOrder = false;
break;
}
}
visiting.remove(c);
hasOrder[c - 'a'] = currHasOrder;
order.push(c);
return currHasOrder;
}
private boolean buildGraph(String[] words, Map<Character, Set<Character>> graph) {
// "aa" must appear before "aac"
String prev = words[0];
String curr;
for (int i = 1; i < words.length; i++) {
curr = words[i];
int k;
for (k = 0; k < Math.min(prev.length(), curr.length()); k++) {
if (prev.charAt(k) != curr.charAt(k)) {
graph.get(prev.charAt(k)).add(curr.charAt(k));
break;
}
}
//curr is prefix of prev
if (prev.length() > curr.length() && k == curr.length()) return false;
//if (k == prev.length()) -> prev is prefix of curr
//no need to add any new edge
prev = curr;
}
return true;
}
}
No comments:
Post a Comment