damien5314
BAN USERJava solution for minimum height tree question.
private static <T> Node<T> getBalancedRoot(Node<T> node) {
// Variables to cache the longest and second longest adjacent paths
Stack<Node<T>> longest = new Stack<>();
Stack<Node<T>> longest2 = new Stack<>();
// Loop through each adjacent node
for (Node<T> connection : node.adjacent) {
// Get the longest path for that child node
Stack<Node<T>> childPath = getLongestPath(connection, node);
// Adjust cached longest paths accordingly
if (childPath.size() > longest.size()) {
longest2 = longest;
longest = childPath;
} else if (childPath.size() > longest2.size()) {
longest2 = childPath;
}
}
// Set the returned root node to our originating node, for now
Node<T> root = node;
int diff = longest.size() - longest2.size();
// If the difference in size between the adjacent paths is more than 1 node, we need to rebalance
while (diff > 1) {
// This is equivalent to moving one node over, e.g.
// 5 3 9 1 (7) 4 2 --- Difference = 4 - 2 = 2
// becomes
// 5 3 9 (1) 7 4 2 --- Difference = 3 - 3 = 0
root = longest.pop();
diff -= 2;
}
// The node at the start of the longest path is now the root, return it
return root;
}
private static <T> Stack<Node<T>> getLongestPath(Node<T> node, Node<T> previous) {
Stack<Node<T>> longestPath = new Stack<>();
if (!node.adjacent.isEmpty()) {
for (Node<T> adjacent : node.adjacent) {
if (adjacent == previous) continue; // Prevent circular loop
Stack<Node<T>> thisLongest = getLongestPath(adjacent, node);
if (thisLongest.size() > longestPath.size()) {
longestPath = thisLongest;
}
}
}
longestPath.add(node);
return longestPath;
}
@Scott: That is one way to put it, but assuming this is an undirected graph you don't really get specific pointers to the parent and children like you would in a real tree data structure. Just an adjacency list or matrix for each node and you have to find which node would best serve as the root to reduce the height of a depth-first search to a minimum.
Approach 2 is pretty interesting, I will definitely try to implement this and post my solution as graphs are my weakness :(
Pretty similar to what others have posted.
int concatenate(int[] nums) {
String[] nums2 = new String[nums.length];
int j = 0;
for (int a : nums) nums2[j++] = String.valueOf(a);
Comparator<String> c = (s1, s2) -> {
for (int i = 0; i < Math.max(s1.length(), s2.length()); i++) {
int i1 = Math.min(s1.length()-1, i);
int i2 = Math.min(s2.length()-1, i);
char n1 = s1.charAt(i1);
char n2 = s2.charAt(i2);
if (n1 != n2) return n2 - n1;
}
return 0;
};
Arrays.sort(nums2, c);
StringBuilder result = new StringBuilder();
for (String s : nums2) result.append(s);
return Integer.valueOf(result.toString());
}
public class TransformWithDictionary {
public static Integer getMinTransformations(String[] dictionary, String start, String end) {
// Construct Map of words to a Set of their adjacent words in the dictionary
Map<String, Set<String>> adjacent = new HashMap<>();
for (String s : dictionary) {
Set<String> adjacentWords = new HashSet<>();
for (String s2 : dictionary) {
if (s == s2) continue;
if (isOneEditAway(s, s2)) adjacentWords.add(s2);
}
adjacent.put(s, adjacentWords);
}
return getMinTransformations(adjacent, start, end, null, 0);
}
/**
* Checks if start can be transformed into end by changing no more than one letter
*/
public static boolean isOneEditAway(String start, String end) {
if (start == null || end == null) return false;
int edits = 0;
int index = 0;
while (edits < 2 && index < end.length()) {
if (start.charAt(index) != end.charAt(index)) edits++;
index++;
}
return edits == 1;
}
public static Integer getMinTransformations(Map<String, Set<String>> dictionary, String start, String end,
Integer min, int steps) {
if (min != null && steps == min) return null; // This path is already longer than the min, just return null
Set<String> adjacentWords = dictionary.get(start);
if (adjacentWords == null) return null; // No adjacent words remaining, return null
if (adjacentWords.contains(end)) return 1; // Base case
// Remove the current word from dictionary to prevent an endless loop
dictionary.remove(start);
// Loop through adjacent words looking for min transformation steps
for (String word : adjacentWords) {
Integer result = getMinTransformations(dictionary, word, end, min, steps + 1);
if (result != null) {
min = min == null ? result + 1 : Math.min(min, result + 1);
}
}
// Finally, return the minimum number of transformations we found
return min;
}
public static void main(String[] args) {
String[] dictionary = new String[] {
"cat", "dog", "pog", "bog", "cot", "all", "yew", "nit", "cog", "raw", "sew", "mow", "saw", "was", "pam",
"sam", "lit", "bit", "wit", "vim", "war", "rat", "mat", "log", "cow", "paw" };
System.out.println("pog -> dog = " + getMinTransformations(dictionary, "pog", "dog")); // 1
System.out.println("pam -> saw = " + getMinTransformations(dictionary, "pam", "saw")); // 2
System.out.println("cat -> dog = " + getMinTransformations(dictionary, "cat", "dog")); // 3
System.out.println("sam -> lit = " + getMinTransformations(dictionary, "sam", "lit")); // null
}
}
Java implementation of Tarjan's algorithm:
- damien5314 December 03, 2015