ഓരോ പ്രതീകവും മാറ്റിസ്ഥാപിക്കുന്ന ചോദ്യത്തിന് ശേഷം പലിൻഡ്രോം പരിശോധിക്കുക  


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക് ഫ്ലിപ്പ്കാർട്ട് ഗൂഗിൾ നെറ്റ്ഫിക്സ്
ഹാഷ് സ്ട്രിംഗ്

“ഓരോ പ്രതീകവും മാറ്റിസ്ഥാപിക്കുന്ന ചോദ്യത്തിന് ശേഷം പലിൻഡ്രോമിനായി പരിശോധിക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് കരുതുന്നു സ്ട്രിംഗ് ഇല്ല. ചോദ്യങ്ങളിൽ, ഓരോ ചോദ്യത്തിനും രണ്ടെണ്ണം ഉണ്ട് പൂർണ്ണസംഖ്യ ഇൻപുട്ട് മൂല്യങ്ങൾ i1 ഒപ്പം i2 ഒപ്പം 'ch' എന്ന് വിളിക്കുന്ന ഒരു പ്രതീക ഇൻപുട്ടും. തന്നിരിക്കുന്ന പ്രതീകമായ 'ch' ഉപയോഗിച്ച് i1, i2 സൂചികകളിലെ മൂല്യങ്ങൾ മാറ്റാനും അത് ഒരു പലിൻഡ്രോം ആണോ എന്ന് നിർണ്ണയിക്കാനും പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

കുറിപ്പ്: 0 <i1 നേക്കാൾ കുറവോ തുല്യമോ ആണ്, കൂടാതെ i2 സ്ട്രിംഗിന്റെ നീളത്തേക്കാൾ കുറവോ തുല്യമോ ആണ്.

ഉദാഹരണം  

ഓരോ പ്രതീകവും മാറ്റിസ്ഥാപിക്കുന്ന ചോദ്യത്തിന് ശേഷം പലിൻഡ്രോം പരിശോധിക്കുകമൊട്ടുസൂചി

String: india, Query=2.
Query 1: i1 = 0, i2 = 4, ch = i
Query 2: i1 = 1, i2 = 3, ch = n
Query 1: No
Query 2: Yes

വിശദീകരണം

ചോദ്യം 1: മാറ്റിസ്ഥാപിച്ചതിനുശേഷം ഇന്ത്യ മാറുന്നു

ചോദ്യം 2: ഇൻ‌ഡി മാറ്റിസ്ഥാപിച്ചതിന് ശേഷം ഇൻ‌ഡി ആയി മാറുന്നു

String: english, Query=3.
Query 1: i1 = 0, i2 = 6, ch = e
Query 2: i1 = 1, i2 = 5, ch = s
Query 3: i1 = 2, i2 = 4, ch = i
Query 1: No
Query 2: No
Query 3: Yes

വിശദീകരണം

ചോദ്യം 1: മാറ്റിസ്ഥാപിച്ചതിന് ശേഷം ഇംഗ്ലീഷ് മാറുന്നു

ചോദ്യം 2: മാറ്റിസ്ഥാപിക്കൽ എസ്‌ഗ്ലൈസിനുശേഷം ഇംഗ്ലീഷ് മാറുന്നു

ചോദ്യം 3: മാറ്റിസ്ഥാപിക്കൽ എസിലൈസിനുശേഷം എസ്‌ഗ്ലൈസ് മാറുന്നു

അൽഗോരിതം  

  1. ഒരു പ്രഖ്യാപിക്കുക ഗണം.
  2. ആദ്യ പകുതിയിലെ എല്ലാ അസമമായ സൂചികകളും ഒരു സെറ്റിൽ സംഭരിക്കുക.
  3. മാറ്റാൻ പ്രതീകങ്ങൾ തന്നിരിക്കുന്ന സൂചികയിൽ (i1, i2) നൽകിയിരിക്കുന്ന പ്രതീക മൂല്യങ്ങൾക്കൊപ്പം.
    1. I1> n / 2 ആണോയെന്ന് പരിശോധിക്കുക, i1 = n-1-i1, i2> n / 2 എന്നിവ ശരിയാണെങ്കിൽ ശരിയാണെങ്കിൽ യഥാക്രമം i2 = n-1-i2 ചെയ്യുക.
    2. പകരം സ്ട്രിംഗ് [i1] == str [n-1-i1] മാറ്റിയിട്ടുണ്ടോയെന്ന് പരിശോധിക്കുക, അത് ശരിയാണെന്ന് കണ്ടെത്തിയാൽ, i1 ഒരു സെറ്റിൽ ഉണ്ടോ ഇല്ലയോ എന്ന് പരിശോധിക്കുക, നിലവിലുണ്ടെങ്കിൽ അത് നീക്കംചെയ്യുന്നു.
      1. അല്ലെങ്കിൽ സജ്ജമാക്കാൻ i1 ചേർക്കുക.
    3. I2- നായി ഈ പ്രക്രിയ ആവർത്തിക്കുക.
  4. ഘട്ടം 3 മുതൽ ആകെ ചോദ്യങ്ങളുടെ എണ്ണം വരെ ആവർത്തിക്കുക.
  5. ശൂന്യമാണെങ്കിൽ സജ്ജമാക്കുകയാണെങ്കിൽ അത് പലിൻഡ്രോം ആണ്, അല്ലാത്തപക്ഷം.
ഇതും കാണുക
ഭൂരിപക്ഷ ഘടകം II ലീട്ട്‌കോഡ് പരിഹാരം

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു സ്‌ട്രിംഗും കുറച്ച് ചോദ്യങ്ങളും നൽകിയിട്ടുണ്ട്, അതിൽ ചില സംഖ്യകളും പ്രതീക ഇൻപുട്ട് മൂല്യങ്ങളും അടങ്ങിയിരിക്കുന്നു, തന്നിരിക്കുന്ന പ്രതീകത്തിനൊപ്പം പ്രതീകങ്ങൾ മാറ്റുകയോ മാറ്റിസ്ഥാപിക്കുകയോ ചെയ്യേണ്ടതുണ്ട്, കൂടാതെ ചില സൂചികകളിൽ i1, i2 എന്നിങ്ങനെ നൽകുകയും പിന്നീട് ആവശ്യമുള്ളതിന് ശേഷം ഓരോ ചോദ്യത്തിനും ശേഷം സ്ട്രിംഗ് പാലിൻഡ്രോം ആണോ അല്ലയോ എന്ന് നിർണ്ണയിക്കാൻ. ഉപയോഗിക്കാനാണ് ആശയം ഹാഷിംഗ്. ഈ പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾ സെറ്റ് ഉപയോഗിക്കാൻ പോകുന്നു. ഞങ്ങൾ പ്രത്യേക പ്രവർത്തനം നടത്താൻ പോകുന്നു ഒരു ഫംഗ്ഷൻ ചോദ്യങ്ങൾ എടുക്കുക, മറ്റൊരു പ്രവർത്തനം പലിൻഡ്രോം പരിശോധിക്കുക എന്നതാണ്. അടിസ്ഥാനപരമായി, ആ ഫംഗ്ഷൻ അൽപ്പം ബിറ്റ് ഫാഷനിൽ പ്രവർത്തിക്കുന്നു. ഓരോ കോൾ കാരണം ഞങ്ങൾ ആ ഫംഗ്ഷനിലേക്ക് വിളിക്കുന്നു. സെറ്റ് ശൂന്യമാണോ അല്ലയോ എന്ന് പരിശോധിക്കുമ്പോൾ ഇത് സെറ്റിൽ പ്രവർത്തനങ്ങൾ നടത്തുന്നു. ഇത് ശൂന്യമാണ്, അതിനർത്ഥം സ്ട്രിംഗ് ഒരു പലിൻഡ്രോം ആണ്, അല്ലാത്തപക്ഷം.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

സ്ട്രിംഗ്: ഇന്ത്യ, അന്വേഷണം = 2, അതായത് i1, i2, ch എന്നിവയുടെ ഇൻപുട്ടുകൾ 2 തവണ എടുക്കും.

സ്ട്രിംഗിന്റെ ആദ്യ പകുതിയിലെ അസമമായ സൂചികകൾ ഞങ്ങൾ സംഭരിക്കേണ്ടതുണ്ട്

അതിനാൽ മുഴുവൻ സ്ട്രിംഗിലൂടെയും സഞ്ചരിച്ച ശേഷം, നമുക്ക് ഇതുപോലെയുള്ള സെറ്റ് ലഭിക്കും,

സജ്ജമാക്കുക: [0, 1]

ആദ്യ ചോദ്യത്തിന്, i1 = 1, i0 = 2, ch = i, സ്ട്രിംഗ് “india” “indii” ആയി മാറുന്നു.

i1 i1 ആയി 0 ആയി തുടരുന്നു, i2 0 ആയി മാറുന്നു, ആദ്യം, i1 കടന്നുപോകുകയും str [i1] == str [n-1-i1] ആണോ എന്ന് പരിശോധിക്കുകയും ചെയ്യും, ഇത് ശരിയാണ്, തുടർന്ന് ഒരു സെറ്റിൽ i1 ഉണ്ടോ എന്ന് പരിശോധിക്കും, അത് ഇത് നിലവിലുണ്ട്, അതിനാൽ ഇത് സെറ്റിൽ നിന്ന് i1 എന്നാൽ 0 നീക്കംചെയ്യും.

അപ്പോൾ i2 ഉം 0 ആയതിനാൽ ഒന്നും സംഭവിക്കില്ല.

ഇതും കാണുക
തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ ഉൽപ്പന്നമുള്ള ട്രിപ്പിളുകളുടെ എണ്ണം എണ്ണുക

രണ്ടാമത്തെ ചോദ്യത്തിന്, i2 = 1, i1 = 2, ch = n, സ്ട്രിംഗ് “indii” “indni” ആയി മാറുന്നു.

i1 i1 ആയി 1 ആയി തുടരുന്നു, i2 1 ആയി മാറുന്നു, ആദ്യം, i1 കടന്നുപോകുകയും str [i1] == str [n-1-i1] ആണോ എന്ന് പരിശോധിക്കുകയും ചെയ്യും, ഇത് ശരിയാണ്, തുടർന്ന് i1 ഒരു സെറ്റിൽ ഉണ്ടോ എന്ന് പരിശോധിക്കും, അത് ഇത് നിലവിലുണ്ട്, അതിനാൽ ഇത് സെറ്റിൽ നിന്ന് i1 എന്നാൽ 1 നീക്കംചെയ്യും. നടത്തിയ എല്ലാ ചോദ്യങ്ങൾക്കും ശേഷം സെറ്റ് ശൂന്യമാണോയെന്ന് പരിശോധിക്കും, ഇപ്പോൾ അത് ശൂന്യമാണോ, അതെ എന്ന് പ്രിന്റുചെയ്യും, കാരണം ഒരു സെറ്റിൽ 0, 1 എന്നീ രണ്ട് മൂല്യങ്ങളുണ്ടായിരുന്നു, ഞങ്ങൾ ഇവ രണ്ടും നീക്കംചെയ്തു.

ഓരോ പ്രതീകവും മാറ്റിസ്ഥാപിക്കുന്ന ചോദ്യത്തിന് ശേഷം പലിൻഡ്രോം പരിശോധിക്കുന്നതിനുള്ള സി ++ കോഡ്  

#include<unordered_set>
#include<iostream>

using namespace std;
void checkPalindrome(string &str, int index, int n,unordered_set<int> &SET)
{
    if (str[index] == str[n-1-index])
    {
        if (SET.find(index) != SET.end())
            SET.erase(SET.find(index)) ;
    }
    else
        SET.insert(index);
}
void getQuery(string &str, int query)
{
    int n = str.length();
    unordered_set<int> SET;
    for (int i=0; i<n/2; i++)
        if (str[i] != str[n-1-i])
            SET.insert(i);

    for (int QueryNo=1; QueryNo<=query; QueryNo++)
    {
        cout << "Values for query " << QueryNo <<endl;
        int i1, i2;
        char ch;
        cout << "Enter i1 ";
        cin >> i1;
        cout << "Enter i2 ";
        cin >> i2;
        cout << "Enter ch ";
        cin >> ch;

        str[i1] = str [i2] = ch;

        if (i1 > n/2)
            i1 = n- 1 -i1;
        if (i2 > n/2)
            i2 = n -1 - i2;

        checkPalindrome(str, i1, n, SET );
        checkPalindrome(str, i2, n, SET );

        cout << "Output for query " << QueryNo << " => ";
        SET.empty()? cout << "YES"<<endl<<endl : cout << "NO"<<endl<<endl;
    }
}
int main()
{
    string str = "india";
    int query = 2 ;
    getQuery(str, query);
    return 0;
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

ഓരോ പ്രതീകവും മാറ്റിസ്ഥാപിക്കുന്ന ചോദ്യത്തിന് ശേഷം പലിൻഡ്രോം പരിശോധിക്കുന്നതിനുള്ള ജാവ കോഡ്  

import java.util.Scanner;
import java.util.HashSet;

class SearchPalindrome
{
    private static Scanner sc=new Scanner(System.in);
    public static void checkPalindrome(String str, int i, int n,HashSet<Integer> SET)
    {
        if (str.charAt(i) == str.charAt(n-1-i))
        {
            if (SET.contains(i))
                SET.remove(i) ;
        }
        else
            SET.add(i);
    }
    public static void Query(String str, int Q)
    {
        int n = str.length();
        HashSet<Integer> SET=new HashSet<>();
        for (int i=0; i<n/2; i++)
            if (str.charAt(i) != str.charAt(n-1-i))
                SET.add(i);

        for (int query=1; query<=Q; query++)
        {
      System.out.println("Values for query " + query);
            int i1, i2;
            char ch;
            System.out.print("Enter i1 " );
            i1=sc.nextInt();
            System.out.print("Enter i2 ");
            i2=sc.nextInt();
            System.out.print("Enter ch ");
            ch=sc.next().charAt(0);


            char[] strChars = str.toCharArray();
            strChars[i1] = ch;

            strChars[i2] = ch;
            str = String.valueOf(strChars);

            if (i1 > n/2)
                i1 = n- 1 -i1;
            if (i2 > n/2)
                i2 = n -1 - i2;

            checkPalindrome(str, i1, n, SET );
            checkPalindrome(str, i2, n, SET );

            System.out.print("Output for query " + query + " => ");

            if(SET.isEmpty())
                System.out.println("YES\n\n");
            else
                System.out.println("NO\n");
        }
    }
    public static void main(String args[])
    {
        String str = "india";
        int query = 2 ;
        Query(str, query);

    }
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

സങ്കീർണ്ണത വിശകലനം  

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

O (Q + N) എവിടെ "Q" ചോദ്യങ്ങളുടെ എണ്ണം കൂടാതെ "N" സ്ട്രിംഗിന്റെ നീളം. ആദ്യം മുതൽ ഞങ്ങൾ സ്ട്രിംഗിന്റെ പകുതി ദൈർഘ്യം വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുകയും മാപ്പിൽ എല്ലാ അസമമായ സൂചികകളും ചേർക്കുകയും തുടർന്ന് O (1) സമയം എടുക്കുന്ന ചോദ്യങ്ങൾ കണക്കുകൂട്ടുകയും ചെയ്യുന്നു. സമയ സങ്കീർണ്ണത രേഖീയമായി മാറുന്നു.

ഇതും കാണുക
സ്റ്റുഡന്റ് അറ്റൻഡൻസ് റെക്കോർഡ് I ലീറ്റ്കോഡ് പരിഹാരം

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ ഇൻപുട്ട് സീക്വൻസിന്റെ ഘടകങ്ങൾ മാപ്പിലേക്ക് ചേർക്കുന്നു. ഏറ്റവും മോശം അവസ്ഥയിൽ, എല്ലാ സൂചികകളിലും നമുക്ക് എല്ലാ അസമമായ പ്രതീകങ്ങളും ഉണ്ടാകാം. ഇത് ഞങ്ങൾക്ക് ഒരു O (N) ഇടം നൽകും.