#題目

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.

public class Solution {
    public char FindTheDifference(string s, string t) {
        
    }
}

#解題

案例一

[TestMethod()]
public void FindTheDifferenceTest_輸入S為abcd_輸入T為abcde()
{
    //arrange
    var sut = new Solution();
    var S = "abcd";
    var T = "abcde";

    char expected = 'e';

    //act
    var actual = sut.FindTheDifference(S, T);

    //assert
    actual.Should().Be(expected);
}

public char FindTheDifference(string s, string t)
{
    var originalString =  s.ToCharArray();

    var addSomeSaltString = t.ToCharArray();

    for (int i = 0; i < addSomeSaltString.Length; i++)
    {
        var checkThisChar = addSomeSaltString[i];
        if (i > originalString.Length -1)
        {
            return checkThisChar;
        }

        if (originalString[i] != checkThisChar)
        {
            return checkThisChar;
        }
    }

    return '\0';
}

#解析

LeetCode跑測試錯誤

補上錯誤案例

[TestMethod()]
public void FindTheDifferenceTest_LeetCode_Error1()
{
    //arrange
    var sut = new Solution();
    var S = "ymbgaraibkfmvocpizdydugvalagaivdbfsfbepeyccqfepzvtpyxtbadkhmwmoswrcxnargtlswqemafandgkmydtimuzvjwxvlfwlhvkrgcsithaqlcvrihrwqkpjdhgfgreqoxzfvhjzojhghfwbvpfzectwwhexthbsndovxejsntmjihchaotbgcysfdaojkjldprwyrnischrgmtvjcorypvopfmegizfkvudubnejzfqffvgdoxohuinkyygbdzmshvyqyhsozwvlhevfepdvafgkqpkmcsikfyxczcovrmwqxxbnhfzcjjcpgzjjfateajnnvlbwhyppdleahgaypxidkpwmfqwqyofwdqgxhjaxvyrzupfwesmxbjszolgwqvfiozofncbohduqgiswuiyddmwlwubetyaummenkdfptjczxemryuotrrymrfdxtrebpbjtpnuhsbnovhectpjhfhahbqrfbyxggobsweefcwxpqsspyssrmdhuelkkvyjxswjwofngpwfxvknkjviiavorwyfzlnktmfwxkvwkrwdcxjfzikdyswsuxegmhtnxjraqrdchaauazfhtklxsksbhwgjphgbasfnlwqwukprgvihntsyymdrfovaszjywuqygpvjtvlsvvqbvzsmgweiayhlubnbsitvfxawhfmfiatxvqrcwjshvovxknnxnyyfexqycrlyksderlqarqhkxyaqwlwoqcribumrqjtelhwdvaiysgjlvksrfvjlcaiwrirtkkxbwgicyhvakxgdjwnwmubkiazdjkfmotglclqndqjxethoutvjchjbkoasnnfbgrnycucfpeovruguzumgmgddqwjgdvaujhyqsqtoexmnfuluaqbxoofvotvfoiexbnprrxptchmlctzgqtkivsilwgwgvpidpvasurraqfkcmxhdapjrlrnkbklwkrvoaziznlpor";

    var T = "qhxepbshlrhoecdaodgpousbzfcqjxulatciapuftffahhlmxbufgjuxstfjvljybfxnenlacmjqoymvamphpxnolwijwcecgwbcjhgdybfffwoygikvoecdggplfohemfypxfsvdrseyhmvkoovxhdvoavsqqbrsqrkqhbtmgwaurgisloqjixfwfvwtszcxwktkwesaxsmhsvlitegrlzkvfqoiiwxbzskzoewbkxtphapavbyvhzvgrrfriddnsrftfowhdanvhjvurhljmpxvpddxmzfgwwpkjrfgqptrmumoemhfpojnxzwlrxkcafvbhlwrapubhveattfifsmiounhqusvhywnxhwrgamgnesxmzliyzisqrwvkiyderyotxhwspqrrkeczjysfujvovsfcfouykcqyjoobfdgnlswfzjmyucaxuaslzwfnetekymrwbvponiaojdqnbmboldvvitamntwnyaeppjaohwkrisrlrgwcjqqgxeqerjrbapfzurcwxhcwzugcgnirkkrxdthtbmdqgvqxilllrsbwjhwqszrjtzyetwubdrlyakzxcveufvhqugyawvkivwonvmrgnchkzdysngqdibhkyboyftxcvvjoggecjsajbuqkjjxfvynrjsnvtfvgpgveycxidhhfauvjovmnbqgoxsafknluyimkczykwdgvqwlvvgdmufxdypwnajkncoynqticfetcdafvtqszuwfmrdggifokwmkgzuxnhncmnsstffqpqbplypapctctfhqpihavligbrutxmmygiyaklqtakdidvnvrjfteazeqmbgklrgrorudayokxptswwkcircwuhcavhdparjfkjypkyxhbgwxbkvpvrtzjaetahmxevmkhdfyidhrdeejapfbafwmdqjqszwnwzgclitdhlnkaiyldwkwwzvhyorgbysyjbxsspnjdewjxbhpsvj";

    char expected = 't';

    //act
    var actual = sut.FindTheDifference(S, T);

    //assert
    actual.Should().Be(expected);
}

顯然我的方向上完全錯誤，題目的意思是兩邊的每種字元個數應該會一樣，唯獨T會多插入一個隨機字元，找出那一個隨機字元，且與排序無關。

原本分別統計S與T包含的每個字元個數後，比較個數不一樣的即是多出來的(~~程式就不寫了，這種暴力破解法大家都會~~)，但總覺得哪裡不對，參考了LeetCode上面大大的答案後果然有更好的解法

將S與T的每個字元用ASCII內碼對應的數字相加後，差即為多出來的數字

public char FindTheDifference(string s, string t)
{
    int sumS = 0;
    foreach (char c in t)
    {
        sumS += c;
    }
    foreach (char c in s)
    {
        sumS -= c;
    }
    return (char)(sumS);
}

在這邊我學習到了

String直接Foreach即是Char的型別(我一開始還在那拆解)
Char可以直接與Int相加，無須轉換

#優化

既然都知道T一定只比S多一個字元，那這樣雙迴圈其實也可以省略掉

public char FindTheDifference(string s, string t)
{
    //先加T的最後一個字元
    int sum = t[t.Length -1];

    for (int i = 0; i < t.Length - 1; i++)
    {
        //T加總
        sum += t[i];
        //扣掉S
        sum -= s[i];

    }
    //相差的值
    return (char)(sum);
}

透過 ^= 運算子

這邊也看到另一種做法，是透過**^= ** (XOR)的運算

Wiki

在數位邏輯中，邏輯算符互斥或閘（exclusive or）是對兩個運算元的一種邏輯分析類型，符號為XOR或EOR或⊕。與一般的邏輯或OR不同，當兩兩數值相同為否，而數值不同時為真。

二進位舉例

1111 ^ 1111 = 0000

0000 ^ 0000 = 0000

0101 ^ 1101 = 1000

var a = 1;
a ^= 5;
//a:4

a ^= 5;
//a:1

var a = 1;
a ^= 2;
//a:3 

a ^= 2;
//a:1

所以碰到相同的數字會被返回來的特性下，可以將程式改成

public char FindTheDifference(string s, string t)
{
    //先加T的最後一個字元
    int sum = t[t.Length -1];

    for (int i = 0; i < t.Length - 1; i++)
    {
        sum ^= t[i];
        sum ^= s[i];

    }
    return (char)(sum);
}

這題雖然被標註為Easy，但果然一些基礎還是要多加強，否則對弱弱的我來說還是不Easy

程式隨筆

【LeetCode】Find the Difference

#題目

#解題

案例一

#解析

補上錯誤案例

#優化

透過 ^= 運算子