ஒவ்வொரு எழுத்துக்குறி மாற்று வினவலுக்கும் பிறகு பாலிண்ட்ரோம் சரிபார்க்கவும்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் , Flipkart கூகிள் நெட்ஃபிக்ஸ்
ஹாஷ் சரம்

“ஒவ்வொரு எழுத்துக்குறி மாற்ற வினவலுக்கும் பிறகு பாலிண்ட்ரோம் சரிபார்க்கவும்” என்ற சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று வைத்துக் கொள்ளுங்கள் சரம் மற்றும் இல்லை. வினவல்களில், ஒவ்வொரு வினவலுக்கும் இரண்டு உள்ளன முழு உள்ளீட்டு மதிப்புகள் 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. இப்போது str [i1] == str [n-1-i1] மாற்றப்பட்ட பிறகு சரிபார்க்கவும், அது உண்மை எனக் கண்டறியப்பட்டால், i1 ஒரு தொகுப்பில் இருக்கிறதா இல்லையா என்பதைச் சரிபார்க்கவும், இருந்தால் அதை அகற்றவும்.
      1. அமைக்க i1 ஐ சேர்க்கவும்.
    3. I2 க்கும் இந்த செயல்முறையை மீண்டும் செய்யவும்.
  4. கொடுக்கப்பட்ட மொத்த கேள்விகளின் எண்ணிக்கை வரை படி 3 முதல் மீண்டும் செய்யவும்.
  5. காலியாக இருந்தால் அமைத்தால் அது பாலிண்ட்ரோம் இல்லையென்றால் அது இல்லை.

விளக்கம்

எங்களுக்கு ஒரு சரம் மற்றும் சில கேள்விகள் வழங்கப்பட்டுள்ளன, அதில் சில முழு எண் மற்றும் எழுத்து உள்ளீட்டு மதிப்புகள் உள்ளன, கொடுக்கப்பட்ட எழுத்துடன் எழுத்துக்களை மாற்றவோ அல்லது மாற்றவோ வேண்டும் மற்றும் சில குறியீடுகளில் i1 மற்றும் i2 என வழங்கப்படுகின்றன, பின்னர் நமக்கு தேவைப்பட்ட பிறகு உருவாக்கப்பட்ட சரம் பாலிண்ட்ரோம் அல்லது ஒவ்வொரு வினவலுக்குப் பிறகும் இல்லையா என்பதை தீர்மானிக்க. யோசனை பயன்படுத்த வேண்டும் ஹாஷிங். இந்த சிக்கலை தீர்க்க செட் பயன்படுத்தப் போகிறோம். நாம் தனித்தனி செயல்பாட்டை உருவாக்கப் போகிறோம் ஒரு செயல்பாடு வினவல்களை எடுத்துக்கொள்வது மற்றும் மற்றொரு செயல்பாடு பாலிண்ட்ரோம் சரிபார்க்க வேண்டும். அடிப்படையில், அந்த செயல்பாடு பிட் பாணியில் ஒரு பிட் வேலை செய்கிறது. ஒவ்வொரு அழைப்பின் காரணமாகவும் நாம் அந்த செயல்பாட்டைச் செய்கிறோம். இது செட்டில் செயல்பாடுகளைச் செய்கிறது மற்றும் செட் காலியாக இருக்கிறதா இல்லையா என்பதைச் சரிபார்க்கும்போது அதற்கு பதிலாக. இது காலியாக உள்ளது, அதாவது சரம் ஒரு பாலிண்ட்ரோம், இல்லையெனில் அது இல்லை.

ஒரு உதாரணத்தைக் கருத்தில் கொள்வோம்:

உதாரணமாக

சரம்: இந்தியா, வினவல் = 2, அதாவது i1, i2 மற்றும் ch இன் உள்ளீடுகளை 2 முறை எடுக்கும்.

சரத்தின் முதல் பாதியின் சமமற்ற குறியீடுகளை நாம் சேமிக்க வேண்டும்

எனவே முழு சரத்தையும் கடந்து சென்ற பிறகு, இது போன்ற செட் இருக்கும்,

அமை: [0, 1]

1 வது வினவலுக்கு, i1 = 0, i2 = 4, ch = i, அதாவது சரம் “india” “indii” ஆக மாறுகிறது.

i1 i1 ஐ 0 ஆகவும், i2 0 ஆகவும், முதலில், i1 கடந்து, str [i1] == str [n-1-i1] என்பதை சரிபார்க்கும், அது உண்மைதான், பின்னர் அது ஒரு தொகுப்பில் i1 இருக்கிறதா என்று சோதிக்கும், அது இது உள்ளது, எனவே இது தொகுப்பிலிருந்து i1 அதாவது 0 ஐ அகற்றும்.

பின்னர் i2 கூட 0 ஆக இருப்பதால் எதுவும் நடக்காது.

2 வது வினவலுக்கு, i1 = 1, i2 = 3, 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) எங்கே "கே" வினவல்களின் எண்ணிக்கை மற்றும் “என்” இது சரத்தின் நீளம். முதலில் நாம் சரத்தின் அரை நீளம் வரை ஒரு சுழற்சியை இயக்கி, அனைத்து சமமற்ற குறியீடுகளையும் வரைபடத்தில் சேர்த்து, பின்னர் O (1) நேரத்தை தனித்தனியாக எடுக்கும் கேள்விகளைக் கணக்கிடுங்கள். நேர சிக்கலானது நேரியல் ஆகிறது.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் நாங்கள் உள்ளீட்டு வரிசையின் கூறுகளை வரைபடத்தில் சேர்ப்போம். மிக மோசமான நிலையில், எல்லா குறியீடுகளிலும் சமமற்ற எழுத்துக்கள் அனைத்தையும் நாம் கொண்டிருக்கலாம். இது எங்களுக்கு O (N) இடத்தை செலவழிக்கும்.