Epoch

題目

  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.

題意

  有兩個字串 s, t，t 會比 s 在隨機位置多一個不同的字母，找出是哪個字母。

想法

  在 t 中找出 s 的字母，並將 t 找到的改為 -1，最後不是 -1 的就是不同的字母。但這個想法用兩個 for 迴圈，這樣複雜度是 O(n^2)，所以 TLE。

  想法二，是用一個 array 紀錄 s 各個字母出現幾次，也記錄 t 的字母出現幾次，最後比較不同的即為所求。

步驟

  1. 統計 s 中，各字母的數量

  2. 統計 t 中，個字母的數量

  3. 找出不同的

程式碼

  char findTheDifference(char* s, char* t) {
    int i;
    int ss[26];
    char ret;
    memset(ss, 0, sizeof(ss));
    for(i=0; i<strlen(s); i++){
        ss[s[i]-97]++;
    }
    for(i=0; i<strlen(t); i++){
        ss[t[i]-97]--;
    }
    for(i=0; i<26; i++){
        if(ss[i]==-1)
            ret = i+97;
    }
    return ret;
    
}