દરેક પાત્રની ફેરબદલ ક્વેરી પછી પેલિન્ડ્રોમ માટે તપાસો


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેસબુક ફ્લિપકાર્ટ Google Netflix
હેશ શબ્દમાળા

સમસ્યા "દરેક પાત્રની ફેરબદલ ક્વેરી પછી પેલિન્ડ્રોમ માટે તપાસો" કહે છે કે ધારો કે તમને એ શબ્દમાળા અને ના. ક્વેરીઝની, દરેક ક્વેરીમાં બે હોય છે પૂર્ણાંક ઇનપુટ કિંમતો તરીકે i1 અને i2 અને એક અક્ષર ઇનપુટ જેને '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: એન્ગ્લીઝ રિપ્લેસમેન્ટ એસિગ્લાઇઝ પછી બને છે

ક્વેરી g: રિપ્લેસમેન્ટ એસિલીઝ પછી એસિગ્લાઇઝ બને છે

અલ્ગોરિધમ

  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 તરીકે આપવામાં આવે છે અને પછી આપણી જરૂરિયાત પછી નિર્ધારિત કરવા માટે કે શું સ્ટ્રિંગ રચાયેલ છે પેલિંડ્રોમ છે કે નહીં તે દરેક ક્વેરી કર્યા પછી. તેનો ઉપયોગ કરવાનો વિચાર છે હેશીંગ. અમે આ સમસ્યાને હલ કરવા માટે સેટનો ઉપયોગ કરીશું. અમે એક અલગ ફંકશન બનાવવા જઈ રહ્યા છીએ એક ફંક્શન ક્વેરીઝ લેવાનું છે અને બીજું ફંક્શન પેલિંડ્રોમ તપાસવાનું છે. મૂળભૂત રીતે, તે ફંક્શન બીટ બાય ફેશનમાં કામ કરે છે. દરેક ક callલને કારણે અમે તે ફંક્શનમાં કરીએ છીએ. તે સેટ પર perપરેશન કરે છે અને બદલામાં જ્યારે આપણે તપાસ કરીએ કે સેટ ખાલી છે કે નહીં. તે ખાલી છે તેનો અર્થ એ છે કે શબ્દમાળા એક પેલિંડ્રોમ છે, નહીં તો તે નથી.

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ:

ઉદાહરણ

શબ્દમાળા: ભારત, ક્વેરી = 2, એટલે કે તે i1, i2 અને ch નો ઇનપુટ્સ લેશે 2 વખત.

આપણે શબ્દમાળાના પહેલા ભાગના અસમાન સૂચકાંકો સંગ્રહિત કરવાની જરૂર છે

તેથી આખા શબ્દમાળાને કા tra્યા પછી, આપણી પાસે આ પ્રમાણે સેટ હશે,

સેટ કરો: [0, 1]

1 લી ક્વેરી માટે, i1 = 0, i2 = 4, ch = i, એટલે શબ્દમાળા “ભારત” “indii” થાય છે.

i1 i1 0 તરીકે રહે છે, i2 0 બને છે, પ્રથમ, i1 પસાર થશે અને તપાસશે કે str [i1] == str [n-1-i1], તે સાચું છે, તે પછી તપાસ કરશે i1 સમૂહમાં હાજર છે, તે પણ હાજર છે, તેથી તે સમૂહમાંથી i1 નો અર્થ 0 દૂર કરશે.

પછી આઇ 2 પણ 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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (ક્યૂ + એન) જ્યાં "પ્ર" પ્રશ્નોની સંખ્યા છે અને “એન” શબ્દમાળા ની લંબાઈ છે. પહેલાથી આપણે શબ્દમાળાની અડધા લંબાઈ સુધી લૂપ ચલાવીએ છીએ અને નકશામાં બધા અસમાન સૂચકાંકો ઉમેરીએ છીએ અને પછી ક્વેરીઓની ગણતરી કરીએ છીએ જે વ્યક્તિગત રીતે ઓ (1) સમય લે છે. સમયની જટિલતા રેખીય બને છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે નકશામાં ઇનપુટ ક્રમના તત્વો ઉમેરી રહ્યા છીએ. અને સૌથી ખરાબ કિસ્સામાં, આપણને બધા સૂચકાંકોમાં બધા અસમાન અક્ષરો હોઈ શકે છે. આના માટે અમારી પાસે ઓ (એન) જગ્યા ખર્ચ થશે.