अंतर Leetcode समाधान खोजें


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना गूगल
hashing तार

इस समस्या में, हमें दो दिए गए हैं तार। दूसरे स्ट्रिंग को पहले स्ट्रिंग के पात्रों को बेतरतीब ढंग से फेरबदल करके और फिर किसी भी यादृच्छिक स्थिति में एक अतिरिक्त चरित्र जोड़कर उत्पन्न किया जाता है। हमें अतिरिक्त चरित्र को वापस करने की आवश्यकता है जिसे दूसरी स्ट्रिंग में जोड़ा गया था। अक्षर हमेशा कम अक्षर वाले अंग्रेजी अक्षर होंगे।

उदाहरण

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

स्पष्टीकरण # 1

अतिरिक्त वर्ण जो स्ट्रिंग में जोड़ा जाता है b स्ट्रिंग के रूप में 'एफ' है a इसमें सम्‍मिलित नहीं है।

स्पष्टीकरण # 2

तार स्ट्रिंग करते समय 4 'a' अक्षर होते हैं has 5. तो, अतिरिक्त पत्र 'a' है।

दृष्टिकोण (छंटनी)

हम दोनों स्ट्रिंग्स को सॉर्ट कर सकते हैं और फिर उन दोनों को अक्षर द्वारा टाइप कर सकते हैं जहां वे अलग-अलग हैं। दूसरा तार हमेशा एक होगा अतिरिक्त चरित्र। तो, हम हमेशा एक बिंदु पाएंगे जहां स्ट्रिंग a और b अलग है। हालांकि, एक मामला हो सकता है जहां स्ट्रिंग b छँटाई के बाद स्ट्रिंग में हर वर्ण से मेल खाता है a लेकिन अंत में एक अतिरिक्त चरित्र है। हमें इस एक विशेष मामले को संभालने की जरूरत है।

अंतर Leetcode समाधान खोजें

कलन विधि

  1. दोनों तारों को क्रमबद्ध करें, a और b। जैसा कि जावा में संभव नहीं है, हम पहले उन्हें में परिवर्तित करते हैं चार सरणियाँ
  2. छोटी स्ट्रिंग में मौजूद प्रत्येक वर्ण के लिए, हम एक पत्र-दर-अक्षर जांच करते हैं:
    • यदि स्ट्रिंग में चरित्र स्ट्रिंग में संबंधित वर्ण के बराबर नहीं है b:
      • इस चरित्र को वापस करो।
  3. स्ट्रिंग का अंतिम वर्ण लौटाएं जैसा कि यह अतिरिक्त चरित्र है
  4. परिणाम प्रिंट करें

अंतर Leetcode समाधान का कार्यान्वयन

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

जावा प्रोग्राम

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

अंतर Leetcode समाधान खोजने की जटिलता विश्लेषण

समय जटिलता

O (NlogN), जहां N = लंबी स्ट्रिंग की लंबाई। हम स्ट्रिंग्स / चार सरणियों को सॉर्ट करते हैं जो O (NlogN) समय लेते हैं।

अंतरिक्ष की जटिलता

पर) जावा में और ओ (1) C ++ में हम स्ट्रिंग्स को कन्वर्ट करते हैं चार सरणियाँ जावा में

दृष्टिकोण (हैशिंग)

दोनों तारों में, हम हर वर्ण को उसकी आवृत्ति के साथ हैश कर सकते हैं और उस वर्ण को खोज सकते हैं जो आवृत्ति में भिन्न हो। चूंकि हमारे पास अद्वितीय पात्रों की एक निरंतर संख्या है। यह एल्गोरिथ्म ऊपर चर्चा की गई की तुलना में तेज़ है। एक कुशल कार्यान्वयन के रूप में, हम एक बना सकते हैं हैश टेबल और स्ट्रिंग में प्रत्येक वर्ण के लिए आवृत्ति बढ़ाना a और स्ट्रिंग में हर वर्ण के लिए आवृत्ति में वृद्धि b. यह हमें ऐसे मामले में छोड़ देगा जहां वास्तव में एक चरित्र की आवृत्ति होती है गैर शून्य और यह स्ट्रिंग में अतिरिक्त चरित्र होगा b.

कलन विधि

  1. सभी वर्णों की आवृत्ति को संग्रहीत करने के लिए एक हैश तालिका प्रारंभ करें आवृत्ति
  2. स्ट्रिंग में हर किरदार के लिए a:
    • हैश तालिका में अपनी आवृत्ति बढ़ाना
  3. स्ट्रिंग में हर किरदार के लिए b:
    • हैश तालिका में इसकी आवृत्ति घट जाती है
    • यदि इसकी आवृत्ति बराबर होती है -1:
      • इस चरित्र को वापस करो
  4. फ़ंक्शन सिंटैक्स बनाए रखने के लिए '-' लौटें
  5. परिणाम प्रिंट करें

अंतर Leetcode समाधान का कार्यान्वयन

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

जावा प्रोग्राम

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

अंतर Leetcode समाधान खोजने की जटिलता विश्लेषण

समय जटिलता

पर), एन = लंबी स्ट्रिंग का आकार, जैसा कि हम अपने चरित्र आवृत्तियों को अपडेट करने के लिए एक बार दोनों तारों के माध्यम से पार करते हैं।

अंतरिक्ष की जटिलता

ओ (1)। यद्यपि हम वर्णों को उनकी आवृत्तियों के साथ संग्रहीत करने के लिए हैशटेबल का उपयोग करते हैं, हम इनपुट के बावजूद निरंतर स्थान का उपयोग करते हैं। तो, अंतरिक्ष की जटिलता निरंतर है।