வேறுபாடு லீட்கோட் தீர்வைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் கூகிள்
ஹேஷிங் சரம்

இந்த சிக்கலில், எங்களுக்கு இரண்டு வழங்கப்படுகிறது சரங்களை. இரண்டாவது சரம் முதல் சரத்தின் எழுத்துக்களை தோராயமாக மாற்றுவதன் மூலம் உருவாக்கப்படுகிறது, பின்னர் எந்த சீரற்ற நிலையிலும் கூடுதல் எழுத்தை சேர்ப்பது. இரண்டாவது சரத்தில் சேர்க்கப்பட்ட கூடுதல் எழுத்தை நாம் திருப்பித் தர வேண்டும். எழுத்துக்கள் எப்போதும் சிறிய எழுத்து ஆங்கில எழுத்துக்களாக இருக்கும்.

உதாரணமாக

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

விளக்கம் # 1

சரத்தில் சேர்க்கப்படும் கூடுதல் எழுத்து b 'f' என்பது சரம் a அதைக் கொண்டிருக்கவில்லை.

விளக்கம் # 2

சரம் சரம் போது 4 'a' எழுத்துக்கள் உள்ளன உள்ளது 5. எனவே, கூடுதல் கடிதம் 'a'.

அணுகுமுறை (வரிசைப்படுத்துதல்)

நாம் இரு சரங்களையும் வரிசைப்படுத்தலாம், பின்னர் அவை இரண்டையும் கடிதம் மூலம் மீண்டும் வேறுபடுத்தி முதல் இடத்தைக் கண்டுபிடிக்கலாம். இரண்டாவது சரம் எப்போதும் ஒன்றைக் கொண்டிருக்கும் கூடுதல் தன்மை. எனவே, நாம் எப்போதும் ஒரு புள்ளியைக் கண்டுபிடிப்போம் a மற்றும் b வேறுபடுகிறது. இருப்பினும், சரம் இருக்கும் ஒரு வழக்கு இருக்கலாம் b வரிசைப்படுத்திய பின் ஒவ்வொரு எழுத்துக்கும் சரம் பொருந்துகிறது a இல் ஆனால் ஒரு கூடுதல் தன்மையைக் கொண்டுள்ளது. இந்த ஒரு சிறப்பு வழக்கை நாம் கையாள வேண்டும்.

வேறுபாடு லீட்கோட் தீர்வைக் கண்டறியவும்

அல்காரிதம்

  1. இரண்டு சரங்களையும் வரிசைப்படுத்தவும், 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), அங்கு N = நீண்ட சரத்தின் நீளம். 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

வேறுபாடு லீட்கோட் தீர்வைக் கண்டறிவதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), நீண்ட சரத்தின் N = அளவு, இரு சரங்களின் வழியாகவும் அவற்றின் எழுத்து அதிர்வெண்களைப் புதுப்பிக்க ஒரு முறை பயணிக்கிறோம்.

விண்வெளி சிக்கலானது

ஓ (1). எழுத்துக்களை அவற்றின் அதிர்வெண்களுடன் சேமிக்க ஒரு ஹேஷ்டேபிளைப் பயன்படுத்தினாலும், உள்ளீட்டைப் பொருட்படுத்தாமல் நிலையான இடத்தைப் பயன்படுத்துகிறோம். எனவே, விண்வெளி சிக்கலானது நிலையானது.