फरक लीटकोड सोल्यूशन शोधा


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन Google
हॅशिंग

समस्या विधान

"फरक शोधा" या समस्येमध्ये आम्हाला दोन दिले आहेत स्ट्रिंग्स एस आणि टी. स्ट्रिंग टी ही यादृच्छिकपणे स्ट्रिंग्जची अक्षरे भरण्याद्वारे आणि यादृच्छिक स्थितीत एक वर्ण जोडून तयार केली जाते.

आपले कार्य स्ट्रिंग टी मध्ये समाविष्ट केलेले वर्ण शोधणे आहे.

उदाहरण

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

स्पष्टीकरण:

फरक लीटकोड सोल्यूशन शोधा

स्ट्रिंग टी चे कॅरेक्टर पुन्हा व्यवस्थित केल्यावर ते “abcde” होते. “Abcd” स्ट्रिंग s मध्ये आधीपासूनच अस्तित्वात आहे, म्हणून t मध्ये जोडलेले अक्षर “e” आहे.

फरक लीटकोड सोल्यूशनसाठी क्रमवारी लावणे

जर आपण समस्या पाहण्यासाठी आपला दृष्टीकोन बदलला तर कधीकधी तो सोडवणे सोपे होते. जसे की येथे समस्या म्हणते की स्ट्रिंग टी शफ्लिंग स्ट्रिंग आणि एक घटक यादृच्छिक स्थितीत जोडून तयार होते. तर आपण स्ट्रिंग टी मध्ये यादृच्छिक स्थानावर कॅरेक्टर जोडून स्ट्रिंग टी तयार केल्याचे दिसेल. जिथे स्ट्रिंग टी चे अक्षर स्ट्रिंग टी च्या कॅरेक्टरशी जुळत नाही तिथेच आपल्याला हे शोधणे आवश्यक आहे आणि मग त्या पोजीशनवर असलेले कॅरॅक्टर परत मिळू शकतो. तर आम्ही या चरणांचे अनुसरण करूः

  1. दोन्ही स्ट्रिंगची क्रमवारी लावा.
  2. वर्ण आणि वर्ण दोन्ही जुळत नाही जेथे वर्ण जुळले आहे ते जोडलेले वर्ण आहे आणि ते उत्तर आहे.
  3. जर सर्व अक्षरे जुळली तर स्ट्रिंग टी च्या शेवटच्या स्थानावरील वर्ण आमचे उत्तर आहे.

अंमलबजावणी

फरक शोधण्यासाठी सी ++ कोड

#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

भेद लीटकोड सोल्यूशनचे गुंतागुंत विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (nlogn) कारण आम्ही दोन्ही स्ट्रिंग सॉर्ट करत आहोत. येथे n दिलेली स्ट्रिंग s ची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे O (n) जावा सोल्यूशनसाठी कारण आम्ही स्ट्रिंगला अ‍ॅरे मध्ये रुपांतरित करत आहोत पण सी ++ साठी हे ओ (1) आहे कारण यामुळे स्टिंगची जागी क्रमवारी लावता येते.

फरक लीटकोड सोल्यूशनसाठी हॅशिंग अ‍ॅप्रोच

आम्ही या चरणांचे अनुसरण करू:

  1. वर्णांची वारंवारिता संचयित करण्यासाठी 26 आकाराचे एक वारंवारता अ‍ॅरे तयार करा. आपण 0 ने प्रारंभ करू.
  2. स्ट्रिंग ओलांडून वारंवारता अ‍ॅरमध्ये वर्णांची वारंवारता संचयित करा.
  3. आता स्ट्रिंग टी ओलांडून वारंवारता अ‍ॅरेपासून स्ट्रिंग टीच्या ट्रॅव्हर्सल दरम्यान आपल्यास आलेल्या प्रत्येक वर्णांची वारंवारता कमी करा.
  4. शेवटी, फ्रिक्वेन्सी अ‍ॅरेचा आढावा घ्या आणि व्हॅल्यू एक असलेल्या स्थितीशी संबंधित वर्ण जोडलेले वर्ण आहे आणि ते आवश्यक उत्तर आहे.

अंमलबजावणी

फरक शोधण्यासाठी सी ++ कोड

#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

भेद लीटकोड सोल्यूशनचे गुंतागुंत विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही फक्त एकदाच तारांना वळवत आहोत. येथे n दिलेल्या स्ट्रिंगची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही वारंवारतेच्या अ‍ॅरेसाठी निरंतर जागा वापरत आहोत.

संदर्भ