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:
1 2 3 4 5 6 7 8 9
Input: s = "abcd" t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.
O(n + 1) time O(26) space array solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14
publicclassSolution{ publiccharfindTheDifference(String s, String t){ int[] counts = newint[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } for (char c : t.toCharArray()) { if (--counts[c - 'a'] < 0) { return c; } } return0; } }
O(n + 1) time O(1) space bit solution
1 2 3 4 5 6 7 8 9 10 11 12
publicclassSolution{ publiccharfindTheDifference(String s, String t){ char res = 0; for (char c : s.toCharArray()) { res ^= c; } for (char c : t.toCharArray()) { res ^= c; } return res; } }