તફાવત લીટકોડ સોલ્યુશન શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન Google
હેશિંગ શબ્દમાળા

આ સમસ્યામાં, અમને બે આપવામાં આવે છે શબ્દમાળાઓ. પ્રથમ શબ્દમાળાના અક્ષરોને અવ્યવસ્થિત રીતે શફલિંગ કરીને અને પછી કોઈપણ રેન્ડમ સ્થિતિમાં વધારાના અક્ષર ઉમેરીને બીજો શબ્દમાળા પેદા થાય છે. અમારે બીજા શબ્દમાળામાં ઉમેરવામાં આવેલા વધારાના પાત્રને પાછા આપવાની જરૂર છે. અક્ષરો હંમેશા લોઅર-કેસ અંગ્રેજી અક્ષરોના રહેશે.

ઉદાહરણ

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

સમજૂતી # 1

વધારાની પાત્ર કે જે શબ્દમાળામાં ઉમેરવામાં આવે છે b શબ્દમાળા તરીકે 'f' છે a તે સમાવતું નથી.

સમજૂતી # 2

શબ્દમાળા શબ્દમાળા દરમિયાન 4 'a' અક્ષરો છે ધરાવે છે. તેથી, વધારાના અક્ષર 'એ' છે.

અભિગમ (સortર્ટિંગ)

આપણે બંને શબ્દમાળાઓને સ sortર્ટ કરી શકીએ છીએ અને પછી બંનેને અક્ષર દ્વારા અક્ષર દ્વારા પુનરાવર્તિત કરી શકીએ છીએ જ્યાં તેઓ અલગ હોય તે પ્રથમ સ્થાન શોધવા માટે. બીજા શબ્દમાળા હંમેશાં એક રહેશે વધારાની પાત્ર તેથી, આપણે હંમેશાં એક બિંદુ શોધીશું જ્યાં શબ્દમાળા a અને b અલગ પડે છે. જો કે, ત્યાં એક કેસ હોઈ શકે છે જ્યાં શબ્દમાળા b સ sortર્ટિંગ પછી શબ્દમાળા દરેક પાત્ર સાથે મેળ ખાય છે a માં પરંતુ અંતે એક વધારાનું પાત્ર છે. આપણે આ એક ખાસ કેસ સંભાળવાની જરૂર છે.

તફાવત લીટકોડ સોલ્યુશન શોધો

અલ્ગોરિધમ

  1. બંને તારને સortર્ટ કરો, a અને b. જાવામાં શક્ય ન હોવાથી, આપણે પહેલા તેમને રૂપાંતરિત કરીએ છીએ ચાર એરે
  2. ટૂંકા શબ્દમાળામાં હાજર દરેક પાત્ર માટે, અમે પત્ર દ્વારા અક્ષરની તપાસ કરીએ છીએ:
    • જો શબ્દમાળા અક્ષર શબ્દમાળાના અનુરૂપ પાત્રની બરાબર નથી b:
      • આ પાત્ર પાછા.
  3. શબ્દમાળાના છેલ્લા પાત્રને પાછા ફરો કારણ કે તે વધારાના પાત્ર છે
  4. પરિણામ છાપો

તફાવત લીટકોડ સોલ્યુશન શોધોનું અમલીકરણ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

જાવા પ્રોગ્રામ

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

તફાવત લીટકોડ સોલ્યુશન શોધોનું જટિલતા વિશ્લેષણ

સમય જટિલતા

O (NlogN), જ્યાં એન = લાંબી તારની લંબાઈ. અમે શબ્દમાળાઓ / ચાર એરેને સ sortર્ટ કરીએ છીએ જે O (NlogN) સમય લે છે.

જગ્યાની જટિલતા

ઓ (એન) જાવા અને ઓ (1) સી ++ માં આપણે શબ્દમાળાઓને કન્વર્ટ કરીએ છીએ ચાર એરે જાવામાં.

અભિગમ (હેશિંગ)

બંને તારમાં, આપણે દરેક પાત્રને તેની આવર્તનથી હેશ કરી શકીએ છીએ અને આવર્તનથી ભિન્ન પાત્ર શોધી શકીએ છીએ. કારણ કે આપણી પાસે સતત સંખ્યાબંધ અનન્ય પાત્રો છે. આ અલ્ગોરિધમનો ઉપરની ચર્ચા કરતા ઝડપી છે. કાર્યક્ષમ અમલીકરણ તરીકે, આપણે એક બનાવી શકીએ છીએ હેશ ટેબલ અને શબ્દમાળા દરેક પાત્ર માટે આવર્તન વધારો a અને શબ્દમાળા દરેક પાત્ર માટે આવર્તન ઘટાડો b. આ આપણને એવા કિસ્સામાં છોડી દેશે જ્યાં બરાબર એક પાત્રની આવર્તન હોય શૂન્ય અને આ શબ્દમાળામાં અતિરિક્ત પાત્ર હશે b.

અલ્ગોરિધમ

  1. બધા અક્ષરોની આવર્તનને સંગ્રહિત કરવા માટે હેશ ટેબલનો પ્રારંભ કરો આવર્તન
  2. શબ્દમાળા દરેક પાત્ર માટે a:
    • હેશ ટેબલમાં તેની આવર્તન વધારવી
  3. શબ્દમાળા દરેક પાત્ર માટે b:
    • હેશ ટેબલમાં તેની આવર્તન ઘટાડો
    • જો તેની આવર્તન બરાબર છે -1:
      • આ પાત્ર પાછા
  4. ફંક્શન સિન્ટેક્સને જાળવવા માટે '-' પાછા ફરો
  5. પરિણામ છાપો

તફાવત લીટકોડ સોલ્યુશન શોધોનું અમલીકરણ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

જાવા પ્રોગ્રામ

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

તફાવત લીટકોડ સોલ્યુશન શોધોનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), એન = લાંબી શબ્દમાળાઓનું કદ, કારણ કે આપણે તેના પાત્ર ફ્રીક્વન્સીઝને અપડેટ કરવા માટે એકવાર બંને શબ્દમાળાઓમાંથી પસાર થઈશું.

જગ્યાની જટિલતા

ઓ (1). તેમ છતાં આપણે તેમની ફ્રીક્વન્સીઝ સાથે અક્ષરો સંગ્રહિત કરવા માટે હેશટેબલનો ઉપયોગ કરીએ છીએ, અમે ઇનપુટને ધ્યાનમાં લીધા વિના સતત જગ્યાનો ઉપયોગ કરીએ છીએ. તેથી, જગ્યાની જટિલતા સતત છે.