yuanlixin49
BAN USERimport java.util.ArrayList;
import java.util.HashMap;
public class Graph
{
ArrayList<Letter> nodes = new ArrayList<Letter>();
HashMap<Character, Letter> map = new HashMap<Character, Letter>();
public Letter addOrCreateNode(char c)
{
if (!map.containsKey(c))
{
Letter node = new Letter(c);
nodes.add(node);
map.put(c, node);
}
return map.get(c);
}
public void addDependency(char c, char nextChar)
{
Letter letter = addOrCreateNode(c);
Letter nextSibling = addOrCreateNode(nextChar);
letter.addNextSibling(nextSibling);
}
public ArrayList<Letter> getNodes()
{
return this.nodes;
}
}
import java.util.ArrayList;
import java.util.Stack;
public class LeetDictionaryTest
{
public static Graph buildGraph(String[] dictionary)
{
Graph graph = new Graph();
int arrLen = dictionary.length;
for (int i = 0; i < arrLen - 1; i++)
{
String word1 = dictionary[i];
String word2 = dictionary[i + 1];
int compareLen = Math.min(word1.length(), word2.length());
for (int j = 0; j < compareLen; j++)
{
if (word1.charAt(j) != word2.charAt(j))
{
graph.addDependency(word1.charAt(j), word2.charAt(j));
}
}
}
return graph;
}
public static Stack<Letter> getOrder(Graph graph)
{
Stack<Letter> stack = new Stack<Letter>();
ArrayList<Letter> letters = graph.getNodes();
for (Letter letter : letters)
{
if (letter.getState() == Letter.State.UNVISTITED)
{
if (!DFS(letter, stack))
{
return null;
}
}
}
return stack;
}
public static boolean DFS(Letter letter, Stack<Letter> stack)
{
if (letter.getState() == Letter.State.VISITING)
{
return false;
}
if (letter.getState() == Letter.State.UNVISTITED)
{
letter.setState(Letter.State.VISITING);
for (Letter l : letter.getSibling())
{
if (!DFS(l, stack))
{
return false;
}
}
letter.setState(Letter.State.VISITED);
stack.push(letter);
}
return true;
}
public static void printStack(Stack<Letter> stack)
{
while (!stack.isEmpty())
{
System.out.print(stack.pop().getName());
System.out.print(" ");
}
}
public static void main(String[] args)
{
String[] dictionary = { "wrt", "wrf", "er", "ett", "rftt" };
Graph graph = buildGraph(dictionary);
Stack<Letter> stack = getOrder(graph);
if (stack == null)
{
System.out.println("Circular error occurred;");
}
else
{
printStack(stack);
}
}
}
- yuanlixin49 June 15, 2018