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.
Follow up: 如果连续两个character不相同，有没有办法优化，比如
abababacba
ababababa
[Solution]
[Solution #1] Hash Table
[Solution #2] ASCII code
这个解法有时候不太容易想到。
[Solution #3] xor 也可以做
[Solution #4] – follow up, binary search
只有连续两个characters不相同，才能用binary search。
否则如果mid相同的话，无法确定extra character在哪边，比如：
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 ' ';

  }

}

Read full article from Google – Find the Extra Character