Below is my code where s1 is larger and s2 is smaller
string paddedString(string s1, string s2){
int min = INT32_MAX, t, star = 0, diff = int(s1.size() - s2.size());
string result = "";
for (int i = 0; i <= diff; i++) {
t = 0;
for (int j = i; j < s2.size(); j++) {
if (s1[j] != s2[j]) {
t++;
}
}
if (t < min) {
min = t;
star = i;
}
}
for (int i = 0; i < star; i++) {
result += "*";
}
result += s2;
for (int i = 0; i < (diff - star); i++) {
result += "*";
}
return result;
}
Prateek Khandelwal
Software Engineer in Directi
+91-7042393719
On Wed, Oct 8, 2014 at 12:10 AM, Rishav Mishra <[email protected]>
wrote:
> Hi Vikas and Prateek,
>
> Vikas, the 'd' is arbitrary. The question is simply to return the padded
> string such that the number of similar characters in the padded smaller
> string (which is now equal in length to the bigger string) and the bigger
> string is the minimum.
>
> Prateek, I can understand the solution you mentioned- be great if you can
> send your code.
>
> However, I understand that the smaller string has to be moved (m-n) times
> and each time there are n comparisons. If anybody has any ideas for
> additional optimizations (even with lets say additional space complexity),
> it would be awesome to hear!
>
> On Tue, Oct 7, 2014 at 11:29 PM, Prateek Khandelwal <[email protected]>
> wrote:
>
>> Just think in this manner that put 0 star in front, then 1 star in front
>> and so on and while doing this just compare both the strings. If you are
>> not able to understand just tell me I will mail my code to you.
>>
>> Prateek Khandelwal
>> Software Engineer in Directi
>> +91-7042393719
>>
>> On Tue, Oct 7, 2014 at 11:23 PM, Prateek Khandelwal <[email protected]>
>> wrote:
>>
>>> I think this question can be done in O((m-n)*n) where m is the length of
>>> larger string and n is the length of smaller string
>>>
>>> Prateek Khandelwal
>>> Software Engineer in Directi
>>> +91-7042393719
>>>
>>> On Tue, Oct 7, 2014 at 6:06 PM, vikas <[email protected]>
>>> wrote:
>>>
>>>> question unclear ?What is to be minimize ?
>>>> in given example:
>>>> ca*d*bch
>>>> abc
>>>>
>>>> what is role of "d" ?
>>>>
>>>>
>>>> On Monday, 6 October 2014 22:52:10 UTC+5:30, Rishav wrote:
>>>>>
>>>>> Hi everyone,
>>>>>
>>>>> I was asked this question recently in an interview: Given two strings
>>>>> of unequal length, you have to pad the smaller string (either at the
>>>>> beginning or the end or both, no insertions allowed) with any character
>>>>> you
>>>>> want. The idea is to minimize the index-wise non-similar elements in both
>>>>> the strings.
>>>>>
>>>>> Example:
>>>>> abc
>>>>> cadbch
>>>>>
>>>>> The character we want should be:
>>>>>
>>>>> **abc*, such that the difference is just one(b and c are same for both
>>>>> strings in this position). I only found a solution with O(mn) complexity.
>>>>> Anybody can suggest any optimizations?
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to [email protected].
>>>>
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
