Gil
BAN USERA Simple recursive solution in Java.
Take the head pointer recursively all the way to the end of the list.
Then start to compare the pointer returned by each recursive action (Easier to understand while reading the code)
Code will actually double check the palindrome, can be improved to run only half way.
public class LinkedPalindrome{
// Actual algo is only this method
private Node solve(Node root, Node p) {
if (p != null) {
Node r = solve(root,p.next);
if (r == null || !r.value.equals(p.value)) {
return null;
} else {
if (r.next == null) {
return root;
} else {
return r.next;
}
}
} else
return root;
}
public static class Node {
final String value;
Node next;
public Node(String value, Node next) {
this.value = value;
this.next = next;
}
}
public static void main (String ... args) {
Node root = new Node("a",new Node("b",new Node("c", new Node("b", new Node("a",null)))));
LinkedPalindrome solver = new LinkedPalindrome();
System.out.println(solver.solve(root));
}
public boolean solve(Node root ) {
return solve(root,root) == root;
}
}
Simple brute force attack.
public class Solver {
public static void main(String... args) {
Solver solve = new Solver();
System.out.println(solve.solve("aasasatb"));
System.out.println(solve.solve("abcdbcdff"));
}
public String solve(String a) {
StringBuilder sb = new StringBuilder();
int foundCounter;
int curSize;
for (int index = 0; index < a.length(); index = index + (foundCounter * (curSize+1))) {
foundCounter = 1;
for (curSize =Math.max( (a.length() - index)/ 2,1) ; curSize >= 1 && foundCounter == 1; curSize--) {
for (int i = index + curSize; i < a.length(); i = i + curSize) {
if (a.substring(index, index + curSize).equals(a.substring(i, Math.min(i + curSize, a.length())))) {
foundCounter++;
} else {
break;
}
}
if (foundCounter > 1 || curSize == 1) {
sb.append(foundCounter).append(a.substring(index, index + curSize));
}
}
}
return sb.toString();
}
}
Stack with an internal node that maintains a link (lets call it 'High') to the current highest value node in the stack.
Each time we push in a new node, we compare the new value to the 'High' in the top element. and we choose the higher value for the new node 'High'.
With this, we maintain the 'High' value in O(1) in push and in pop.
----
----
Push O(1)
Pop O(1)
PeekHigh O(1)
----
----
//schematic code, not full code
public class Stack<T> {
private class Node {
T value;
Node next;
Node high;
}
private Node top;
public void push(T value) {
top = new Node(value,top);
if (top.next != null && top.value.compareTo(top.next.value) < 0) {
top.high = top.next;
} else {
top.high = top;
}
}
public T peekHigh() {
return top.high.value;
}
}
Correct.
- Gil June 01, 2015You can reduce some key space if you hold images only in the full B-Tree and add links from the favorites B-Tree nodes to the proper node in the full B-Tree to retrieve the image. Thus avoiding the HashMap all together.
But image space is usually going to be much bigger then key space.