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.
C Solution 1:
char findTheDifference(char* s, char* t) {
int ht[26] = {0};
char *p;
for (p = s; *p; p++) ht[*p - 'a']++;
for (p = t; *p; p++) ht[*p - 'a']--;
int i;
for (i = 0; i < 26 && !ht[i]; i++);
return i + 'a';
}
C Solution 2: Using a 32 bits unsigned integer instead of the array.
char findTheDifference(char* s, char* t) {
uint32_t ht = 0, flag = 1;
char *p;
for (p = s; *p; p++) ht ^= flag << (*p - 'a');
for (p = t; *p; p++) ht ^= flag << (*p - 'a');
char c = 'a';
while (ht >>= 1) c++;
return c;
}
C Solution 3: Bit manipulation (but not a technique of hash table):
char findTheDifference(char* s, char* t) {
char c = 0;
for (; *s; s++) c ^= *s;
for (; *t; t++) c ^= *t;
return c;
}
Summary:
- 0ms, 14.02%
- This problem should be solved with bit manipulation, it's not a typical HashTable problem.
- Same to above problem: 136. Single Number
LeetCode: 389. Find the Difference
近期评论