Garukun
BAN USERObservation:
1) There could be at most one character differ from both Strings.
2) When the strings lengths are equal, the solution is straight forward: advance both charAt pointers at the same time until the the difference is found.
3) When the strings lengths are not equal, off by one we will need to stall pointer of the shorter string when the first difference is found. And after that it should behave like (2).
And the code should look like:
// Java
boolean findSingleCharacterDifference(String left, String right) {
String longer = left.length() > right.length() ? left : right;
String shorter = left.length() > right.length() ? right : left;
boolean stalled = left.length() == right.length();
for (int i = 0; i < shorter.length(); i++) {
if (shorter.charAt(i) != longer.charAt(i)) {
// When we have encountered our first difference, the remaining substring
// must be equal to be true.
int offset = stalled ? 1 : 0;
return shorter.substring(i + 1).equals(longer.substring(i + 1+ offset));
}
}
// Assert left.equals(right), we can choose to add if check at the beginning.
return false;
}
Analysis:
1) We can observe that in a perfectly sorted list, the number of unordered pairs is 0. E.g.
[1 2 3 4 5]
2) If we swapped only one of them, the number of unordered pairs is the number of elements to the left of it. E.g.
[2 3 4 1 5]
In this case, the number of unordered pairs is 3:
[2 1], [3 1], [4 1]
3) Now, we observe the positional difference of the swapped elemented, in the sorted list, it's 0, in the scrambled list, it's 3. The difference seems to be our answer.
4) Let's take a look at a bit more complex example:
[2 5 4 1 3]
The number of unordered pairs is 6. How do we get that number?
Algorithm:
1) Sort the list into a copy of another list used for comparison. (Commonly O(N*log N))
2) Starting from the smallest element in the sorted list and add its positional difference to the final result.
3) Remove this element from both list. (There may be other positional math that doesn't require removing the element, but I'm too lazy to try to figure that out. This I find is very straight-forward to explain the algorithm)
4) Do (2) and (3) for all elements in the list. (O(N))
Time complexity: O(N * log N) + O(N) = O(N * log N)
E.g.
[2 5 4 1 3]
// Sort.
[1 2 3 4 5]
// Iteration 0.
[2 5 4 1 3]
[1 2 3 4 5]
numOfUnorderedPairs = 0;
// Iteration 1.
[2 5 4 3]
[2 3 4 5]
numOfUnorderedPairs = 3;
// Iteration 2.
[5 4 3]
[3 4 5]
numOfUnorderedPairs = 3; // no positional difference.
// Iteration 3.
[5 4]
[4 5]
numOfUnorderedPairs = 5;
// Iteration 4.
[5]
[5]
numOfUnorderedPairs = 6;
// Iteration 5.
[]
[]
numOfUnorderedPairs = 6; // Done.
I'm running short on time when writing this up, so I'll come up with code in a later post.
- Garukun November 03, 2014Classic question. Solution and analysis can be googled with 'leetcode-copy-list-with-random-pointer' keyword.
A solution excerpted from the page above using HashMap.
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode newHead = new RandomListNode(head.label);
RandomListNode p = head;
RandomListNode q = newHead;
map.put(head, newHead);
p = p.next;
while (p != null) {
RandomListNode temp = new RandomListNode(p.label);
map.put(p, temp);
q.next = temp;
q = temp;
p = p.next;
}
p = head;
q = newHead;
while (p != null) {
if (p.random != null)
q.random = map.get(p.random);
else
q.random = null;
p = p.next;
q = q.next;
}
return newHead;
}
Make a copy of the linked list nodes in a hash table where the old nodes is mapped to the new nodes in 1 to 1 fashion.
And then walk through the linked list one more time to replicate the references through looking up the values in the hash table.
Finally, return the new head node.
Miro, you're right, I missed the last TRUE case where xy and xyz are considered the same. That one along with the first one you mentioned are two easy edge cases, I'll update my code as well momentarily.
- Garukun November 05, 2014