LeetCode 389: Find the Difference

Difficulty: Easy

Tags: Hash Table, Bit Manipulation

问题描述

给定2个字符串s和t，t是由s打乱重组并在一个随机位置添加一个字母形成的。

找到那个新添加的字母。

解决方案

利用了字母的ASCII值。

字符串中字母的顺序并不重要。

我们知道t比s多了一个字母，其余字母尽管顺序不同但都是一样的。

那就分别把2个字符串所有的字符相加，然后t的字符和减去s的字符和得到的数字，就是新添加的字符的ASCII值。

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    char findTheDifference(string s, string t) {
        int vs = 0;
        int vt = 0;

        for(int i=0; i<s.size(); i++)
            vs += s[i];

        for(int j=0; j<t.size(); j++)
            vt += t[j];

        char res = vt - vs;

        return res;
    }
};

回到 Conquer Leetcode