## Monday, August 8, 2016

### Google – Find the Extra Character

Google – Find the Extra Character
Given two strings, one of them has one more character than the other, return it.
abababacba
ababababa
[Solution]
[Solution #1] Hash Table
[Solution #2] ASCII code

[Solution #3] xor 也可以做
[Solution #4] – follow up, binary search

aabcccc
aacccc

aaccccc
aacccc

`// ASCII Code solution`
`class` `Solution {`
`  ``public` `char` `extraChar(String s, String t) {`
`    ``if` `(s.length() < t.length()) {`
`      ``return` `extraChar(t, s);`
`    ``}`
`    ``if` `(s.length() - t.length() > ``1``) {`
`      ``throw` `new` `IllegalArgumentException();`
`    ``}`

`    ``int` `result = ``0``;`
`    ``for` `(``char` `c : s.toCharArray()) {`
`      ``result += c;`
`    ``}`
`    ``for` `(``char` `c : t.toCharArray()) {`
`      ``result -= c;`
`    ``}`

`    ``return` `(``char``) result;`
`  ``}`
`}`

`// special case: binary search`
`class` `Solution3 {`
`  ``public` `char` `extraChar(String s, String t) {`
`    ``if` `(s.length() < t.length()) {`
`      ``return` `extraChar(t, s);`
`    ``}`
`    ``int` `l = ``0``;`
`    ``int` `r = s.length() - ``1``;`
`    ``while` `(l <= r) {`
`      ``int` `mid = l + (r - l) / ``2``;`
`      ``if` `(mid >= t.length()) {`
`        ``return` `s.charAt(mid);`
`      ``}`
`      ``if` `(s.charAt(mid) == t.charAt(mid)) {`
`        ``l = mid + ``1``;`
`      ``}`
`      ``else` `{`
`        ``if` `(mid == ``0``) {`
`          ``return` `s.charAt(``0``);`
`        ``}`
`        ``else` `if` `(s.charAt(mid - ``1``) == t.charAt(mid - ``1``)) {`
`          ``return` `s.charAt(mid);`
`        ``}`
`        ``else` `{`
`          ``r = mid - ``1``;`
`        ``}`
`      ``}`
`    ``}`
`    ``return` `' '``;`
`  ``}`
`}`