forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathfind_difference.py
More file actions
37 lines (27 loc) · 962 Bytes
/
find_difference.py
File metadata and controls
37 lines (27 loc) · 962 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
Find the Difference
Given two strings where the second is generated by shuffling the first and
adding one extra letter, find the added letter using XOR.
Reference: https://en.wikipedia.org/wiki/Exclusive_or
Complexity:
Time: O(n) where n is the length of the longer string
Space: O(1)
"""
from __future__ import annotations
def find_difference(original: str, shuffled: str) -> str:
"""Find the single character added to a shuffled copy of a string.
Uses XOR on all character code points; paired characters cancel out,
leaving only the extra character.
Args:
original: The original string.
shuffled: The shuffled string with one extra character.
Returns:
The single character that was added.
Examples:
>>> find_difference("abcd", "abecd")
'e'
"""
xor_result = 0
for character in original + shuffled:
xor_result ^= ord(character)
return chr(xor_result)