తేడా లీట్‌కోడ్ పరిష్కారాన్ని కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ గూగుల్
హ్యాషింగ్

సమస్యల నివేదిక

“తేడాను కనుగొనండి” అనే సమస్యలో మనకు రెండు ఇవ్వబడ్డాయి తీగలను s మరియు టి. స్ట్రింగ్ s యొక్క అక్షరాలను యాదృచ్చికంగా నింపడం మరియు యాదృచ్ఛిక స్థానంలో ఒక అక్షరాన్ని జోడించడం ద్వారా స్ట్రింగ్ t ఉత్పత్తి అవుతుంది.

స్ట్రింగ్ t లో జోడించిన అక్షరాన్ని కనుగొనడం మా పని.

ఉదాహరణ

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

వివరణ:

తేడా లీట్‌కోడ్ పరిష్కారాన్ని కనుగొనండి

స్ట్రింగ్ t యొక్క అక్షరాలను క్రమాన్ని మార్చిన తరువాత అది “abcde” అవుతుంది. “Abcd” ఇప్పటికే స్ట్రింగ్ s లో ఉన్నందున, t కి జోడించబడిన అక్షరం “e”.

తేడా లీట్‌కోడ్ పరిష్కారాన్ని కనుగొనడానికి అప్రోచ్‌ను క్రమబద్ధీకరించడం

సమస్యను చూడటానికి మన దృక్పథాన్ని మార్చుకుంటే, కొన్నిసార్లు దాన్ని పరిష్కరించడం సులభం అవుతుంది. స్ట్రింగ్ s ను షఫ్లింగ్ చేయడం ద్వారా మరియు యాదృచ్ఛిక స్థానంలో ఒక మూలకాన్ని జోడించడం ద్వారా స్ట్రింగ్ t ఉత్పత్తి అవుతుందని ఇక్కడ సమస్య చెబుతుంది. కాబట్టి, స్ట్రింగ్ s లో యాదృచ్ఛిక స్థానం వద్ద అక్షరాన్ని జోడించడం ద్వారా స్ట్రింగ్ t ఉత్పత్తి అవుతున్నందున మనం దీనిని చూడవచ్చు. ఇప్పుడు మనం స్ట్రింగ్ s యొక్క అక్షరం స్ట్రింగ్ t యొక్క అక్షరంతో సరిపోలని స్థానాన్ని మాత్రమే కనుగొనవలసి ఉంటుంది మరియు ఆ స్థానంలో ఉన్న అక్షరాన్ని తిరిగి ఇవ్వవచ్చు. కాబట్టి మేము ఈ దశలను అనుసరిస్తాము:

  1. స్ట్రింగ్ రెండింటినీ క్రమబద్ధీకరించండి.
  2. అక్షరాన్ని బట్టి స్ట్రింగ్ మరియు అవి సరిపోలని పాయింట్ రెండూ అక్షరాలతో తనిఖీ చేయండి జోడించిన అక్షరం మరియు అది సమాధానం.
  3. అన్ని అక్షరాలు సరిపోలితే, స్ట్రింగ్ t యొక్క చివరి స్థానంలో ఉన్న అక్షరం మన సమాధానం.

అమలు

ఫైండ్ ది డిఫరెన్స్ కోసం సి ++ కోడ్

#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 ఇచ్చిన స్ట్రింగ్ యొక్క పొడవు.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత పై) జావా పరిష్కారం కోసం ఎందుకంటే మేము తీగలను శ్రేణిగా మారుస్తున్నాము కాని C ++ కొరకు ఇది O (1) ఎందుకంటే ఇది స్టింగ్ యొక్క స్థల విభజనను అనుమతిస్తుంది.

తేడా లీట్‌కోడ్ పరిష్కారాన్ని కనుగొనడానికి హాషింగ్ అప్రోచ్

మేము ఈ దశలను అనుసరిస్తాము:

  1. అక్షరాల ఫ్రీక్వెన్సీని నిల్వ చేయడానికి పరిమాణం 26 యొక్క ఫ్రీక్వెన్సీ శ్రేణిని సృష్టించండి. మేము దానిని 0 తో ప్రారంభిస్తాము.
  2. స్ట్రింగ్ s లో ప్రయాణించి, ఫ్రీక్వెన్సీ శ్రేణిలో అక్షరాల ఫ్రీక్వెన్సీని నిల్వ చేయండి.
  3. ఇప్పుడు స్ట్రింగ్ టిని దాటండి మరియు ఫ్రీక్వెన్సీ అర్రే నుండి స్ట్రింగ్ టి యొక్క ట్రావెర్సల్ సమయంలో మీరు ఎదుర్కొనే ప్రతి అక్షరం యొక్క ఫ్రీక్వెన్సీని తగ్గించండి.
  4. చివరలో, ఫ్రీక్వెన్సీ శ్రేణిని దాటండి మరియు విలువ XNUMX తో ఉన్న స్థానానికి అనుగుణమైన అక్షరం జోడించిన అక్షరం మరియు అది అవసరమైన సమాధానం.

అమలు

ఫైండ్ ది డిఫరెన్స్ కోసం సి ++ కోడ్

#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

తేడాను కనుగొనడం యొక్క సంక్లిష్టత విశ్లేషణ లీట్‌కోడ్ పరిష్కారం

సమయం సంక్లిష్టత

పై కోడ్ యొక్క సమయం సంక్లిష్టత పై) ఎందుకంటే మేము ఒక్కసారి మాత్రమే తీగలను దాటుతున్నాము. ఇక్కడ n ఇచ్చిన స్ట్రింగ్ యొక్క పొడవు.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (1) ఎందుకంటే మేము ఫ్రీక్వెన్సీ శ్రేణి కోసం స్థిరమైన స్థలాన్ని ఉపయోగిస్తున్నాము.

ప్రస్తావనలు