වෙනස ලීට්කෝඩ් විසඳුම සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් ගූගල්
හැෂිං

ගැටළු ප්රකාශය

“වෙනස සොයාගන්න” යන ගැටලුවේදී අපට දෙකක් ලබා දී ඇත නූල් s සහ ටී. String t නිපදවනු ලබන්නේ අහඹු ලෙස නූල් s හි අකුරු පුරවා එක් අක්ෂරයක් අහඹු ස්ථානයක එකතු කිරීමෙනි.

අපගේ කර්තව්‍යය වන්නේ ටී නූලට එකතු කළ අක්‍ෂරය සොයා ගැනීමයි.

උදාහරණයක්

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

පැහැදිලි කිරීම:

වෙනස ලීට්කෝඩ් විසඳුම සොයා ගන්න

T හි අක්ෂර නැවත සකස් කිරීමෙන් පසු එය “abcde” බවට පත්වේ. “Abcd” දැනටමත් නූල් s වල ඇති බැවින් t ට එකතු කරන ලද අක්‍ෂරය “e” වේ.

වෙනස ලීට්කෝඩ් විසඳුම සොයා ගැනීම සඳහා ප්‍රවේශය වර්ග කිරීම

ගැටලුව බැලීමට අපගේ ඉදිරිදර්ශනය වෙනස් කළහොත් සමහර විට එය විසඳීම පහසු වේ. මෙහි දී මෙන් ගැටළුව පවසන්නේ නූල් ටී උත්පාදනය වන්නේ නූල් මාරු කිරීමෙන් සහ අහඹු ස්ථානයක එක් අංගයක් එකතු කිරීමෙනි. ඉතින්, අපට මෙය දැකිය හැක්කේ, නූල් s හි අහඹු ස්ථානයක අක්ෂරයක් එකතු කිරීමෙන් t t ජනනය වන බැවිනි. දැන් අපට අවශ්‍ය වන්නේ නූල් s හි අක්‍ෂරය t හි අක්ෂරයට නොගැලපෙන ස්ථානය පමණක් සොයා ගැනීමයි, එවිට අපට එම ස්ථානයේ ඇති අක්ෂරය නැවත ලබා දිය හැකිය. එබැවින් අපි මෙම පියවර අනුගමනය කරන්නෙමු:

  1. නූල් දෙකම වර්ග කරන්න.
  2. අක්ෂර අනුව අක්ෂර පරීක්ෂා කරන්න, නූල් සහ ඒවා නොගැලපෙන ස්ථානය එකතු කළ අක්‍ෂරය වන අතර එය පිළිතුරයි.
  3. සියලුම අක්ෂර ගැලපෙන්නේ නම්, t හි අවසාන ස්ථානයේ ඇති අක්‍ෂරය අපගේ පිළිතුරයි.

ක්රියාත්මක කිරීම

වෙනස සොයා ගැනීම සඳහා 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

වෙනස සොයා ගැනීමේ සංකීර්ණතා විශ්ලේෂණය ලීට්කෝඩ් විසඳුම

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ ඕ (nlogn) මොකද අපි නූල් දෙකම වර්ග කරනවා. මෙහි n යනු දී ඇති නූල් වල දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ සාමාන්ය (n) ජාවා ද්‍රාවණය සඳහා අප නූල් අරාව බවට පරිවර්තනය කරන නමුත් C ++ සඳහා එය O (1) නිසා එය ස්ථානීයව වර්ග කිරීම සඳහා ඉඩ ලබා දේ.

වෙනස ලීට්කෝඩ් විසඳුම සොයා ගැනීම සඳහා ප්‍රවේශවීමේ ප්‍රවේශය

අපි මෙම පියවර අනුගමනය කරන්නෙමු:

  1. අක්ෂර සංඛ්‍යාතය ගබඩා කිරීම සඳහා 26 ප්‍රමාණයේ සංඛ්‍යාත අරාවක් සාදන්න. අපි එය 0 සමඟ ආරම්භ කරමු.
  2. නූල් s හරහා ගමන් කර සංඛ්‍යාත අරාවෙහි අක්ෂර සංඛ්‍යාතය ගබඩා කරන්න.
  3. දැන් t නූල හරහා ගමන් කර සංඛ්‍යාත අරාවෙහි සිට t ටී ගමන් කරන විට ඔබට හමු වන එක් එක් අක්ෂරවල සංඛ්‍යාතය අඩු කරන්න.
  4. අවසානයේදී, සංඛ්‍යාත අරාව හරහා ගමන් කරන්න සහ අගය XNUMX සමඟ ඇති ස්ථානයට අනුරූප වන අක්‍ෂරය එකතු කළ අක්‍ෂරය වන අතර එය අවශ්‍ය පිළිතුර වේ.

ක්රියාත්මක කිරීම

වෙනස සොයා ගැනීම සඳහා 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

වෙනස සොයා ගැනීමේ සංකීර්ණතා විශ්ලේෂණය ලීට්කෝඩ් විසඳුම

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ සාමාන්ය (n) මොකද අපි නූල් හරහා ගමන් කරන්නේ එක් වරක් පමණයි. මෙන්න n යනු දී ඇති නූල් වල දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) අපි සංඛ්‍යාත අරාව සඳහා නියත ඉඩක් භාවිතා කරන නිසා.

ආශ්රිත