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


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

समस्या का विवरण

समस्या में "अंतर खोजें" हमें दो दिए गए हैं तार एस और टी। स्ट्रिंग टी को यादृच्छिक रूप से स्ट्रिंग एस के पात्रों को भरकर और यादृच्छिक स्थिति में एक चरित्र को जोड़कर बनाया जाता है।

हमारा काम उस चरित्र का पता लगाना है जो स्ट्रिंग टी में जोड़ा गया था।

उदाहरण

s = "abcd", t = "abcde"
e

स्पष्टीकरण:

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

स्ट्रिंग टी के पात्रों को फिर से व्यवस्थित करने के बाद यह "एब्सर्ड" हो जाता है। जैसा कि "एबीसी" पहले से ही स्ट्रिंग एस में मौजूद है, इसलिए जो चरित्र टी में जोड़ा गया था वह "ई" है।

अंतर Leetcode समाधान खोजने के लिए छँटाई दृष्टिकोण

यदि हम समस्या को देखने के लिए अपना दृष्टिकोण बदलते हैं तो कभी-कभी इसे हल करना आसान हो जाता है। यहाँ समस्या यह कहती है कि स्ट्रिंग t को स्ट्रिंग s के फेरबदल और यादृच्छिक स्थिति में एक तत्व जोड़कर उत्पन्न किया जाता है। इसलिए, हम यह देख सकते हैं कि स्ट्रिंग s में एक यादृच्छिक स्थिति में एक वर्ण जोड़कर स्ट्रिंग टी उत्पन्न की गई है। अब हमें केवल उस स्थिति का पता लगाने की जरूरत है जहां स्ट्रिंग एस का चरित्र स्ट्रिंग टी के चरित्र के साथ मेल नहीं खा रहा है और फिर हम उस स्थिति में मौजूद चरित्र को वापस कर सकते हैं। तो हम इन चरणों का पालन करेंगे:

  1. दोनों स्ट्रिंग को क्रमबद्ध करें।
  2. चरित्र को स्ट्रिंग और बिंदु दोनों से जांचें जहां वे मेल नहीं खाते थे, वह जोड़ा गया वर्ण है और वह उत्तर है।
  3. यदि सभी वर्ण मेल खाते हैं तो स्ट्रिंग टी के अंतिम स्थान पर मौजूद चरित्र हमारा उत्तर है।

कार्यान्वयन

अंतर खोजने के लिए C ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
    
    sort(t.begin(),t.end());
    
    
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
      {
        return t[i];
      }
    }
    
    return t[t.length()-1];
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

अंतर खोजने के लिए जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
    char[] sortedS = s.toCharArray();
    char[] sortedT = t.toCharArray();
    Arrays.sort(sortedS);
    Arrays.sort(sortedT);
    for(int i=0;i<s.length();i++){
      if (sortedS[i] != sortedT[i]) {
        return sortedT[i];
      }
    }

    return sortedT[s.length()];
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

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

समय की जटिलता

उपरोक्त कोड की समय जटिलता है ओ (nlogn) क्योंकि हम दोनों तारों को छांट रहे हैं। यहाँ n दी गई स्ट्रिंग s की लंबाई है।

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

उपरोक्त कोड की अंतरिक्ष जटिलता है पर) जावा समाधान के लिए क्योंकि हम स्ट्रिंग्स को एक सरणी में परिवर्तित कर रहे हैं लेकिन C ++ के लिए यह O (1) है क्योंकि यह स्टिंग के इन-प्लेस सॉर्टिंग की अनुमति देता है।

अंतर Leetcode समाधान खोजने के लिए हैशिंग दृष्टिकोण

हम इन चरणों का पालन करेंगे:

  1. वर्णों की आवृत्ति को संग्रहीत करने के लिए आकार 26 की एक आवृत्ति सरणी बनाएं। हम इसे 0 से आरंभ करेंगे।
  2. स्ट्रिंग s को पार करें और आवृत्ति सरणी में वर्णों की आवृत्ति को संग्रहीत करें।
  3. अब स्ट्रिंग टी को पार करें और आवृत्ति सरणी से स्ट्रिंग टी के ट्रैवर्सल के दौरान आपके द्वारा सामना किए जाने वाले प्रत्येक वर्ण की आवृत्ति को कम करें।
  4. अंत में, फ़्रीक्वेंसी ऐरे और कैरेक्टर को पोज़िशन के साथ उसी स्थिति में लाएँ, जो ऐडेड कैरेक्टर है और यह आवश्यक उत्तर है।

कार्यान्वयन

अंतर खोजने के लिए C ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
      char findTheDifference(string s, string t) {
        int count[26] = {0};
        for(int i=0;i<s.length();i++) count[s[i]-'a']++;
        for(int i=0;i<t.length();i++) count[t[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return 'a';
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

अंतर खोजने के लिए जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
        int[] count = new int[26];
        char[] S = s.toCharArray(), T = t.toCharArray();
        for(int i=0;i<S.length;i++) count[S[i]-'a']++;
        for(int i=0;i<T.length;i++) count[T[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return '\0';
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

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

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम स्ट्रिंग्स को केवल एक बार ट्रेस कर रहे हैं। यहाँ n दी गई स्ट्रिंग की लंबाई है।

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

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

संदर्भ