389-FindtheDifference.md

389. Find the Difference

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Clarification:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.

Solution

解法一

排序之後比對，不一樣就 return

• 時間複雜度：$O(nlogn)$
• 空間複雜度：$O(n)$

解法二(參考)

將兩個字串中的每個字元的 ASCII 碼相加，然後將 t 中多出來的字元的 ASCII 碼減去 s 中所有字元的 ASCII 碼之和，得到的結果就是多出來的那個字元的 ASCII 碼。

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

code

• java

  • Code

    class Solution {
      public char findTheDifference(String s, String t) {
          char[] sCharArray = s.toCharArray();
          Arrays.sort(sCharArray);
          char[] tCharArray = t.toCharArray();
          Arrays.sort(tCharArray);
          for(int i = 0; i < tCharArray.length -1; i++){
              if(sCharArray[i] != tCharArray[i]){
                  return tCharArray[i];
              }
          }
          return tCharArray[t.length() - 1];
      }
      public char findTheDifference_solution2(String s, String t) {
          int sum = 0;
          for(char c : s.toCharArray()){
              sum += c;
          }
          for(char c : t.toCharArray()){
              sum -= c;
          }
          return (char) (-sum);
      }
    
    }