online advertising

Thursday, September 8, 2016

LeetCode OJ - Find the Difference

Problem:

Please find the problem here.

Analysis:

It would be ideal if we can simply scan the two strings once and find it out.

Solution:

We can achieve that by keeping track of the alphabet counts. We decrement the count for an alphabet whenever we see it in the first string and increment it again when we see it in the second string. Whatever alphabet that is left over (i.e. count == 1) is the answer.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/2/problems/find-the-difference/

#include "LEET_FIND_THE_DIFFERENCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FIND_THE_DIFFERENCE
{
    class Solution
    {
    public:
        char findTheDifference(string s, string t)
        {
            int* counts = new int[26];
            for (int i = 0; i < 26; i++)
            {
                counts[i] = 0;
            }
            for (size_t i = 0; i < s.length(); i++)
            {
                counts[s[i] - 'a']--;
            }
            for (size_t i = 0; i < t.length(); i++)
            {
                counts[t[i] - 'a']++;
            }
            for (int i = 0; i < 26; i++)
            {
                if (counts[i] == 1)
                {
                    return i + 'a';
                }
            }
            return 0;
        }
    };
};

using namespace _LEET_FIND_THE_DIFFERENCE;

int LEET_FIND_THE_DIFFERENCE()
{
    Solution solution;
    cout << solution.findTheDifference("abcd", "aecbd") << endl;
    return 0;
}

No comments :

Post a Comment