Find the Difference

Posted on

Problem

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

 

Solution

screen-shot-2016-09-10-at-8-53-55-pm

For problems of finding the difference, first think about XOR operation. Two points about XOR must be comfortable with:

  • 0 ^ A = A
  • XOR is commutable, so sequence not matters

Secondly, think about the length of s and t. t must have one more letter than s. Combined with the commutation of XOR, two XOR operations can be put under the same for loop.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s