Thomas
BAN USERSome missing details. To delete, we need to remember to (1) look up the value to be deleted in the hash table, (2) find the pointer to the corresponding node in the queue, (3) find the pointer to the previous node in the queue, (4) update the previous node's next pointer to point to the node following the deleted node, (5) remove the entry from hash table for the deleted value, (6) look up the value of the node following the deleted node in the hash table, (7) update it's previous pointer to point to the node before the deleted node in the queue.
For dequeue, we also need to look up the value of the node following the deleted node in the hash table and assign its previous pointer to null.
This is a good problem for dynamic programming, which can reduce a brute-force algorithm of O(N^3) down one notch to an algorithm of O(N^2). Look up the Levenshtein algorithm as a related dynamic programming algorithm.
Explanation: We build an N+1 by N matrix and fill in the upper half in this way: the value of an element m[i][j] is the number of characters ending at position i that match the same number of characters ending at position j. In other words, m[i][j] = 1 + m[i-1][j-1] if the ith character matches the jth character, it is 0 otherwise. We only need to fill the upper half of the matrix because of symmetry: the rows and columns both iterate over the same input string. We make an extra row at the top to initialize with zeros which helps us as we start so we have a zero to add our first count onto when iterating over the top row of the matrix.
To know when a match is consecutive, we just compare the count at m[i][j] with it's position in the matrix. The count must be equal to the distance from the diagonal. For example, a single repeating character "a" in the string "baac" is one character long and one character from the diagonal. Hence the check for m[i][j] == j-i+1.
bool findConsecutiveReps(char[] s)
{
int[][] m = new int[s.length + 1][s.length];
// Initialize first row of table
// (This row does not correspond to a character in the string.
for (int j = 0; j < len; j++)
{
m[0][j] = 0;
}
// Row = candidate start position of first substring plus 1.
for (int i = 1; i <= s.length; i++)
{
// Col = candidate start position of second substring.
// Note that when i == j, j is actually the next character after i
// because of the extra row.
for (int j = i; j < s.length; j++)
{
if (s[i-1] == s[j])
{
m[i][j] = 1 + m[i-1][j-1];
if (m[i][j] == j - i + 1)
{
return true;
}
}
else
{
m[i][j] = 0;
}
}
}
return false;
}
Why does the comment say that function f is recursive? It doesn't seem to be calling itself, either directly or indirectly.
And why does the loop inside function f only go half way through the input string?
It looks almost like the brute force approach, except that it has one and half nested loops instead of three. :-) So I guess that makes it half of a brute force approach.
Good job. A brute force algorithm that actually works is certainly better than the submissions above here that don't even work.
But, I think a brute force algorithm for this problem is actually O(N cubed) == O(N^3), including yours, since there are three nested loops iterating over the length of the input, in the worst-case: one loop for start position, one loop for end position, and one loop to check the two sub-strings for equality.
// Java code for flatten, based on pre-order traversal.
// When we visit a node, we append that node to a new linked list.
// No new nodes are created, so we must be careful not to remove
// pointers that might be needed in the pre-order traversal.
// Pass array of size 1 to simulate pass-by-reference in Java.
void preOrderFlatten(Node n, Node[] new)
{
// Loop over nodes of a list.
while (n != null)
{
// Visit node by appending to growing new list.
if (new[0] != null)
{
new[0].next = n;
n.prev = new[0];
}
// Preserve the tail of the growing list.
new[0] = n;
// Recursion.
preOrderFlatten(n.child, new);
// Continue loop.
n = n.next;
}
}
I think the if statement is O(N) because in the worst case you have to iterate over N characters to compare each one.
- Thomas September 08, 2012