389. Find the Difference.md

389. Find the Difference

---

leetcode Daily Challenge on September 24th, 2020.

leetcode-cn Daily Challenge on December 18th, 2020.

---

Difficulty : Easy

Related Topics : HashTable、Bit Manipulation

---

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

• mine
  • Java
    • Runtime: 2 ms, faster than 59.43%, Memory Usage: 39.6 MB, less than 11.76% of Java online submissions

      //O(N)time
      //O(N)space
      public char findTheDifference(String s, String t) {
          int[] record = new int[26];
          for(char c : s.toCharArray()){
              record[c - 'a']++;
          }
          for(char c : t.toCharArray()){
              int i = c - 'a';
              record[i]--;
              if(record[i] < 0) return c;
          }
          return 0;
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 99.41%, Memory Usage: 39.7 MB, less than 10.13% of Java online submissions

  //O(N)time
  //O(N)space
  public char findTheDifference(String s, String t) {
      int sumS = 0, sumT = 0;
      char[] arrS = s.toCharArray();
      char[] arrT = t.toCharArray();
      for (int i = 0; i < arrS.length; i++) {
          sumS += arrS[i] - 'a';
          sumT += arrT[i] - 'a';
      }
      sumT += arrT[arrT.length - 1] - 'a';
      return (char) (sumT - sumS + 'a');
  }
  

---