വ്യത്യാസ ലീറ്റ്കോഡ് പരിഹാരം കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ഗൂഗിൾ
ഹാഷിംഗ് സ്ട്രിംഗ്

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് രണ്ട് നൽകിയിരിക്കുന്നു സ്ട്രിംഗുകൾ. ആദ്യ സ്ട്രിംഗിലെ പ്രതീകങ്ങൾ ക്രമരഹിതമായി മാറ്റിക്കൊണ്ട് ഏതെങ്കിലും ക്രമരഹിതമായ സ്ഥാനത്ത് ഒരു അധിക പ്രതീകം ചേർത്താണ് രണ്ടാമത്തെ സ്ട്രിംഗ് സൃഷ്ടിക്കുന്നത്. രണ്ടാമത്തെ സ്‌ട്രിംഗിലേക്ക് ചേർത്ത അധിക പ്രതീകം ഞങ്ങൾ നൽകേണ്ടതുണ്ട്. പ്രതീകങ്ങൾ എല്ലായ്പ്പോഴും ചെറിയ അക്ഷരങ്ങളുള്ള ഇംഗ്ലീഷ് അക്ഷരങ്ങളായിരിക്കും.

ഉദാഹരണം

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

വിശദീകരണം # 1

സ്‌ട്രിംഗിലേക്ക് ചേർത്ത അധിക പ്രതീകം b സ്ട്രിംഗായി 'f' ആണ് a അതിൽ അടങ്ങിയിട്ടില്ല.

വിശദീകരണം # 2

സ്ട്രിംഗ് സ്‌ട്രിംഗ് സമയത്ത് 4 'എ' അക്ഷരങ്ങളുണ്ട് ഉണ്ട് 5. അതിനാൽ, അധിക അക്ഷരം 'a' ആണ്.

സമീപനം (അടുക്കുന്നു)

നമുക്ക് രണ്ട് സ്ട്രിംഗുകളും അടുക്കി, തുടർന്ന് അവ വ്യത്യാസപ്പെടുന്ന ആദ്യത്തെ സ്ഥാനം കണ്ടെത്താൻ അക്ഷരങ്ങളിലൂടെ അക്ഷരങ്ങൾ ഉപയോഗിച്ച് ആവർത്തിക്കുക. രണ്ടാമത്തെ സ്ട്രിംഗിന് എല്ലായ്പ്പോഴും ഒന്ന് ഉണ്ടായിരിക്കും അധികമായി പ്രതീകം. അതിനാൽ, സ്ട്രിംഗ് ഉള്ള ഒരു പോയിന്റ് ഞങ്ങൾ എല്ലായ്പ്പോഴും കണ്ടെത്തും a ഒപ്പം b വ്യത്യാസപ്പെട്ടിരിക്കുന്നു. എന്നിരുന്നാലും, സ്ട്രിംഗ് ഉള്ള ഒരു കേസ് ഉണ്ടാകാം b അടുക്കിയതിന് ശേഷം സ്ട്രിംഗിലെ എല്ലാ പ്രതീകങ്ങളുമായി പൊരുത്തപ്പെടുന്നു a in എന്നാൽ അവസാനം ഒരു അധിക പ്രതീകമുണ്ട്. ഈ ഒരു പ്രത്യേക കേസ് ഞങ്ങൾ കൈകാര്യം ചെയ്യേണ്ടതുണ്ട്.

വ്യത്യാസ ലീറ്റ്കോഡ് പരിഹാരം കണ്ടെത്തുക

അൽഗോരിതം

  1. രണ്ട് സ്ട്രിംഗുകളും അടുക്കുക, a ഒപ്പം b. ജാവയിൽ ഇത് സാധ്യമല്ലാത്തതിനാൽ, ഞങ്ങൾ ആദ്യം അവയെ പരിവർത്തനം ചെയ്യുന്നു ചാർ അറേകൾ
  2. ഹ്രസ്വമായ സ്‌ട്രിംഗിലുള്ള ഓരോ പ്രതീകത്തിനും, ഞങ്ങൾ ഒരു കത്ത്-ബൈ-ലെറ്റർ പരിശോധന നടത്തുന്നു:
    • സ്‌ട്രിംഗിലെ പ്രതീകമാണെങ്കിൽ സ്‌ട്രിംഗിലെ അനുബന്ധ പ്രതീകത്തിന് തുല്യമല്ല b:
      • ഈ പ്രതീകം നൽകുക.
  3. സ്‌ട്രിംഗിന്റെ അവസാന പ്രതീകം നൽകുക അത് അധിക പ്രതീകമായതിനാൽ
  4. ഫലം അച്ചടിക്കുക

കണ്ടെത്തൽ വ്യത്യാസം ലീറ്റ്കോഡ് പരിഹാരം നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

വ്യത്യാസം കണ്ടെത്തുന്നതിനുള്ള സങ്കീർണ്ണ വിശകലനം ലീറ്റ്കോഡ് പരിഹാരം

സമയ സങ്കീർണ്ണത

O (NlogN), ഇവിടെ N = ദൈർഘ്യമേറിയ സ്‌ട്രിംഗിന്റെ നീളം. O (NlogN) സമയമെടുക്കുന്ന സ്ട്രിംഗുകൾ / ചാർ അറേകൾ ഞങ്ങൾ അടുക്കുന്നു.

സ്ഥല സങ്കീർണ്ണത

O (N) ജാവയിലും O (1) ഞങ്ങൾ സ്ട്രിംഗുകളായി പരിവർത്തനം ചെയ്യുമ്പോൾ C ++ ൽ ചാർ അറേ ജാവയിൽ.

സമീപനം (ഹാഷിംഗ്)

രണ്ട് സ്ട്രിംഗുകളിലും, നമുക്ക് ഓരോ പ്രതീകത്തെയും അതിന്റെ ആവൃത്തി ഉപയോഗിച്ച് ഹാഷ് ചെയ്യാനും ആവൃത്തിയിൽ വ്യത്യാസമുള്ള പ്രതീകം കണ്ടെത്താനും കഴിയും. ഞങ്ങൾക്ക് നിരന്തരമായ അദ്വിതീയ പ്രതീകങ്ങൾ ഉള്ളതിനാൽ. ഈ അൽഗോരിതം മുകളിൽ ചർച്ച ചെയ്തതിനേക്കാൾ വേഗതയേറിയതാണ്. കാര്യക്ഷമമായ നടപ്പാക്കൽ എന്ന നിലയിൽ, നമുക്ക് ഒരു സൃഷ്ടിക്കാൻ കഴിയും ഹാഷ് പട്ടിക ഒപ്പം സ്‌ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും ആവൃത്തി വർദ്ധിപ്പിക്കുക a ഒപ്പം സ്‌ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും ആവൃത്തി കുറയ്‌ക്കുക b. കൃത്യമായി ഒരു പ്രതീകത്തിന്റെ ആവൃത്തി ഉള്ള ഒരു സാഹചര്യത്തിൽ ഇത് ഞങ്ങളെ ഉപേക്ഷിക്കും പൂജ്യമല്ലാത്തത് ഇത് സ്‌ട്രിംഗിലെ അധിക പ്രതീകമായിരിക്കും b.

അൽഗോരിതം

  1. എല്ലാ പ്രതീകങ്ങളുടെയും ആവൃത്തി സംഭരിക്കുന്നതിന് ഒരു ഹാഷ് പട്ടിക സമാരംഭിക്കുക ആവൃത്തി
  2. സ്‌ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും a:
    • ഹാഷ് പട്ടികയിൽ അതിന്റെ ആവൃത്തി വർദ്ധിപ്പിക്കുക
  3. സ്‌ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും b:
    • ഹാഷ് പട്ടികയിൽ അതിന്റെ ആവൃത്തി കുറയ്‌ക്കുക
    • അതിന്റെ ആവൃത്തി തുല്യമാണെങ്കിൽ -1:
      • ഈ പ്രതീകം നൽകുക
  4. ഫംഗ്ഷൻ സിന്റാക്സ് നിലനിർത്താൻ '-' മടങ്ങുക
  5. ഫലം അച്ചടിക്കുക

കണ്ടെത്തൽ വ്യത്യാസം ലീറ്റ്കോഡ് പരിഹാരം നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

വ്യത്യാസം കണ്ടെത്തുന്നതിനുള്ള സങ്കീർണ്ണ വിശകലനം ലീറ്റ്കോഡ് പരിഹാരം

സമയ സങ്കീർണ്ണത

O (N), ദൈർഘ്യമേറിയ സ്‌ട്രിംഗിന്റെ N = വലുപ്പം, രണ്ട് സ്ട്രിംഗുകളിലൂടെയും അവയുടെ പ്രതീക ആവൃത്തികൾ അപ്‌ഡേറ്റുചെയ്യാൻ ഞങ്ങൾ ഒരിക്കൽ സഞ്ചരിക്കുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (1). പ്രതീകങ്ങളുടെ ആവൃത്തി ഉപയോഗിച്ച് സംഭരിക്കാൻ ഞങ്ങൾ ഒരു ഹാഷ്‌ടേബിൾ ഉപയോഗിക്കുന്നുണ്ടെങ്കിലും, ഇൻപുട്ട് പരിഗണിക്കാതെ ഞങ്ങൾ സ്ഥിരമായ ഇടം ഉപയോഗിക്കുന്നു. അതിനാൽ, സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്.