געפֿינען די חילוק לעעטקאָדע לייזונג  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן גוגל
אַלגערידאַמז קאָדירונג האַשינג אינטערוויו interviewprep LeetCode LeetCodeSolutions שטריקל

אין דעם פּראָבלעם, מיר זענען געגעבן צוויי סטרינגס. די רגע שטריקל איז דזשענערייטאַד דורך שאַפלינג די אותיות פון דער ערשטער שטריקל ראַנדאַמלי און דערנאָך לייגן אַן עקסטרע כאַראַקטער אין קיין טראַפ - שטעלע. מיר דאַרפֿן צו צוריקקומען די עקסטרע כאַראַקטער וואָס איז צוגעגעבן צו די רגע שטריקל. די אותיות וועלן שטענדיק זיין קליין-ענגליש אותיות.

בייַשפּיל  

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

דערקלערונג # 1

די עקסטרע כאַראַקטער וואָס איז מוסיף צו שטריקל b איז 'F' ווי שטריקל a טוט נישט אַנטהאַלטן עס.

דערקלערונג # 2

שטריקל האט 4 'אַ' אותיות בשעת שטריקל האט 5. אַזוי, די עקסטרע בריוו איז 'אַ'.

צוגאַנג (סאָרטינג)  

מיר קענען סאָרט ביידע סטרינגס און יטערירן זיי ביידע בריוו פֿאַר בריוו צו געפֿינען די ערשטע שטעלע ווו זיי זענען אַנדערש. די רגע שטריקל וועט שטענדיק האָבן איין עקסטרע כאראקטער. אַזוי, מיר וועלן שטענדיק געפֿינען אַ פונט ווו שטריקל a און b דיפפערס. אָבער, עס קען זיין אַ פאַל אַז שטריקל b נאָך סאָרטינג גלייַכן יעדער כאַראַקטער אין שטריקל a אין אָבער עס האט איין עקסטרע כאַראַקטער אין די סוף. מיר דאַרפֿן צו האַנדלען מיט דעם איין ספּעציעל פאַל.

געפֿינען די חילוק לעעטקאָדע לייזונג

אַלגאָריטהם

  1. סאָרט ביידע די סטרינגס, a און b. ווייַל עס איז ניט מעגלעך אין Java, מיר ערשטער גער זיי אין טשאַר ערייז
  2. פֿאַר יעדער כאַראַקטער אין די קירצער שטריקל, מיר טאָן אַ בריוו-דורך-בריוו קאָנטראָל:
    • אויב דער כאַראַקטער אין שטריקל איז נישט גלייַך צו די קאָראַספּאַנדינג כאַראַקטער אין שטריקל b:
      • צוריקקומען דעם כאַראַקטער.
  3. ווייַזן די לעצטע כאַראַקטער פון שטריקל ווי עס איז די עקסטרע כאַראַקטער
  4. דרוק דעם רעזולטאַט
זע אויך
געפֿינען נומערן מיט אפילו נומער פון דידזשאַץ לעעטקאָדע סאַלושאַן

ימפּלאַמענטיישאַן פון געפֿינען די דיפפערענסע לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון די דיפפערענסע לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (NlogN), ווו N = לענג פון די לאַנג שטריקל. מיר סאָרטירן די סטרינגס / טשאַר ערייז וואָס נעמען אָ (NlogN) צייט.

אָרט קאַמפּלעקסיטי

אָ (N) אין זשאווא און אָ (1) אין C ++ ווען מיר גער די סטרינגס אין טשאַר אַררייַס אין דזשאַוואַ.

צוגאַנג (כאַשינג)  

אין ביידע סטרינגס, מיר קענען האַש יעדער כאַראַקטער מיט זיין אָפטקייַט און געפֿינען די כאַראַקטער וואָס איז אַנדערש אין אָפטקייַט. זינט מיר האָבן אַ קעסיידערדיק נומער פון יינציק אותיות. דער אַלגערידאַם איז פאַסטער ווי די אויבן דיסקאַסט. ווי אַ עפעקטיוו ימפּלאַמענטיישאַן, מיר קענען שאַפֿן אַ האַש טיש און ינקראַמאַנט די אָפטקייַט פֿאַר יעדער כאַראַקטער אין שטריקל a און פאַרקלענערן די אָפטקייַט פֿאַר יעדער כאַראַקטער אין שטריקל b. דאָס וועט לאָזן אונדז אין אַ פאַל אַז די אָפטקייַט פון פּונקט איין כאַראַקטער איז ניט-נול און דאָס וועט זיין די עקסטרע כאַראַקטער אין שטריקל b.

אַלגאָריטהם

  1. יניטיאַליזירן אַ האַש טיש צו קראָם די אָפטקייַט פון אַלע אותיות ווי אָפטקייַט
  2. פֿאַר יעדער כאַראַקטער אין שטריקל a:
    • ינקראַמאַנט די אָפטקייַט אין די האַש טיש
  3. פֿאַר יעדער כאַראַקטער אין שטריקל b:
    • דעקרעמענט זייַן אָפטקייַט אין די האַש טיש
    • אויב די אָפטקייַט איז גלייַך צו -1:
      • צוריקקומען דעם כאַראַקטער
  4. צוריקקומען '-' צו האַלטן פונקציע סינטאַקס
  5. דרוק דעם רעזולטאַט
זע אויך
ציילן און טאַגאַל פֿראגן אויף אַ ביינערי עריי

ימפּלאַמענטיישאַן פון געפֿינען די דיפפערענסע לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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), N = גרייס פון די לאָנגער שטריקל, ווייַל מיר דורכפאָר ביידע סטרינגס אַמאָל צו דערהייַנטיקן זייער כאַראַקטער פריקוואַנסיז.

אָרט קאַמפּלעקסיטי

אָ (1). כאָטש מיר נוצן אַ האַשטאַבלע צו קראָם אותיות מיט זייער פריקוואַנסיז, מיר נוצן קעסיידערדיק פּלאַץ ראַגאַרדלאַס פון די ינפּוט. אַזוי, די פּלאַץ קאַמפּלעקסיטי איז קעסיידערדיק.