Leetcode 389. Find the Difference(找不同)

题意重述

给定两个只由小写字母构成的字符串s和t,t由s打乱顺序后再位于随机位置插入一个字符,找出这个新加入的字符 原题链接

解题思路

异或运算中有自反定理

将s和t的元素两两异或,由于t是由s乱序而来,除了新插入的元素之外t和s具有相同的组成元素,按照自反定理即所剩的元素即为新加入的字符

代码示例:
/*
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.
*/
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    char findTheDifference(std::string s, std::string t) {
        char c = t.at(t.length()-1);
        for(int i=0;i<(t.length()-1);i++)
        {
            c^=s[i];
            c^=t[i];
        }
        return c;
    }
};

int main()
{
    Solution solution;
    std::string a = "abcdefghijk";
    std::string b = "balhidefkgjc";
    char c = solution.findTheDifference(a, b); 
    cout<<c<<endl;
    return 0;
}
示例输出
l

发表评论

电子邮件地址不会被公开。 必填项已用*标注