online advertising

Sunday, May 28, 2017

LeetCode OJ - Permutation in String

Problem:

Please find the problem here.

Analysis:

The idea is that we can check if two strings are equal to each other by comparing their histogram.

Solution:

We can easily compute the histogram of the s2, but for s1, we need a sliding histogram. Fortunately, computing a sliding histogram is pretty easy and simply take $ O(1) $ time to slide it. It is also $ O(1) $ time to compare two histograms since the strings only has lower case letters.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/permutation-in-string

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

using namespace std;

namespace _LEET_PERMUTATION_IN_STRING
{
    class Solution {
    public:
        bool checkInclusion(string s1, string s2)
        {
            if (s1.length() > s2.length())
            {
                return false;
            }
            char fixed_histogram[26];
            char slide_histogram[26];
            for (int i = 0; i < 26; i++)
            {
                fixed_histogram[i] = slide_histogram[i] = 0;
            }
            for (size_t i = 0; i < s1.length(); i++)
            {
                fixed_histogram[s1[i] - 'a']++;
                slide_histogram[s2[i] - 'a']++;
            }
            bool match = true;
            for (int i = 0; match && i < 26; i++)
            {
                match = fixed_histogram[i] == slide_histogram[i];
            }
            if (match)
            {
                return true;
            }
            for (size_t i = s1.length(); i < s2.length(); i++)
            {
                slide_histogram[s2[i - s1.length()] - 'a']--;
                slide_histogram[s2[i] - 'a']++;
                match = true;
                for (int i = 0; match && i < 26; i++)
                {
                    match = fixed_histogram[i] == slide_histogram[i];
                }
                if (match)
                {
                    return true;
                }
            }
            return false;
        }
    };
};

using namespace _LEET_PERMUTATION_IN_STRING;

int LEET_PERMUTATION_IN_STRING()
{
    Solution solution;
    cout << (solution.checkInclusion("ab", "eidbaooo") ? "True" : "False") << endl;
    return 0;
}

No comments :

Post a Comment