هر حرف بدلائڻ واري سوال کان پوءِ Palindrome لاءِ چيڪ ڪريو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon ڪريو فلپٽٽ گوگل Netflix
هاش اسٽرنگ

مسئلو ”Palindrome لاءِ چيڪ ڪريو هر ڪردار جي متبادل واري Query کان پوءِ“ ٻڌائي ٿو ته سمجهو ته توهان کي هڪ ڏني وئي آهي اسٽرنگ ۽ نه. سوالن جا ، هر سوال کي ٻه آهن انٽرويو جيترا قدر valuesڻ i1 ۽ i2 ۽ هڪ ڪردار ان پٽ جنهن کي 'چ' سڏيو ويندو آهي. مسئلو بيان ڪيل ڪردار 'چ' سان I1 ۽ i2 انڊيڪس تي قدر تبديل ڪرڻ لاءِ پڇي ٿو ۽ اهو طئي ڪري ٿو ته اهو هڪ پيلنڊروم آهي يا نه.

نوٽ: 0 <i1 کان گهٽ يا برابر آهي ۽ i2 تار جي ڊيگهه کان گهٽ يا برابر آهي.

مثال

هر حرف بدلائڻ واري سوال کان پوءِ Palindrome لاءِ چيڪ ڪريو

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. انهي عمل کي 2 جي لاءِ ٻيهر ورجايو.
  4. مرحلن 3 کان ورجائي ٿو.
  5. جيڪڏهن سيٽ ڪريو جيڪڏهن خالي آهي ، اهو ٻئي طرف آهي پر اهو نه آهي.

وضاحت

اسان کي هڪ اسٽرنگ ۽ ڪجهه سوالات ڏنا ويا آهن ، جيڪي ان ۾ ڪجهه انٽيگر ۽ ڪردار انپٽ ويليوز تي مشتمل آهن ، اسان کي ڏنل ڪردار سان خاص طور تي ۽ خاص اشارن تي ڪردارن کي تبديل يا بدلائڻ جي ضرورت آهي ، جيڪي I1 ۽ i2 طور ڏنل آهن ۽ پوءِ اهو طئي ڪرڻ لاءِ ته ڇا هر تندار ڪرڻ کان پوءِ تار ٺاهيو ويو آهي يا نه. خيال استعمال ڪرڻ آهي چُڪڻ. اسان هن مسئلي کي حل ڪرڻ لاءِ سيٽ کي استعمال ڪرڻ وارا آهيون. اسان جدا ڪم ڪرڻ وارا آھيون ھڪڙو فنڪشن سوالن کي وٺڻ لاءِ آھي ۽ ٻيو فنڪشن پيلنروم کي چيڪ ڪرڻ آھي. بنيادي طور تي ، اهو فيشن بِٽ فيشن ۾ ٿورڙي طور ڪم ڪري ٿو. هر ڪال جي ڪري اسان انهي ڪارڪردگي ڏانهن گهرايو ٿا. اهو سيٽ تي آپريشن ڪندو آهي ۽ موٽ ۾ جڏهن اسان چيڪ ڪندو ته سيٽ خالي آهي يا نه. اهو خالي آهي ان جو مطلب آهي ته تار هڪ سينڊروم آهي ، ٻيو نه آهي.

اچو ته هڪ مثال تي غور ڪريون.

مثال

اسٽرنگ: انڊيا ، سوال = 2 ، ان جو مطلب آهي ته اهو 1 وقت ، i2 ۽ ch 2 جو انٽ وٺندو.

اسان کي تار جي پهرين اڌ جي اڻ برابري انڊيڪس کي ذخيرو ڪرڻ جي ضرورت آهي

پوء س theي سوراخ کي ڇڪڻ کان پوءِ ، اسان انهي وانگر سيٽ ڪيو هوندو.

سيٽ: [0 ، 1]

پهرين پڇاڻي لاءِ ، i1 = 1 ، i0 = 2 ، ch = i ، معنيٰ اسٽرنگ “انڊيا” بنجي “indii”.

i1 1 طور I0 رهي ٿو ، i2 0 بنجي ٿو ، پهريان ، i1 گذري ٿو ۽ اهو جاچيندو ته str [i1] == str [n-1-i1] ، اهو صحيح آهي ، پوءِ اهو چيڪ ڪندو I1 هڪ سيٽ ۾ موجود آهي ، اهو پڻ موجود آهي ، تنهن ڪري اهو سيٽ تان I1 جو مطلب ڪ removeندو.

پوءِ I2 پڻ 0 آهي تنهنڪري ڪجهه به ٿيڻ وارو ناهي.

ٻئي سوال لاءِ ، i2 = 1 ، i1 = 2 ، ch = n ، معنيٰ اسٽرنگ “انڊي” “انڊن” ٿي وڃي ٿي.

i1 I1 رهي ٿو 1 جي طور تي ، i2 1 بنجي ٿو ، پهريان ، i1 گذري ٿو ۽ چڪاس ٿو ڪري سگھي ٿو str [i1] == str [n-1-i1] ، اهو صحيح آهي ، پوءِ اهو چيڪ ڪندس ته i1 هڪ سيٽ ۾ موجود آهي ، اهو پڻ موجود آهي ، تنهن ڪري اهو سيٽ 1 مان I1 کي ڪ willي ڇڏيندو آهي. ان کانپوءِ سڀني سوالن جي ڪيل هجڻ کانپوءِ اها جانچ ڪندي ته ڇا سيٽ خالي آهي ۽ هاڻي اهو خالي آهي ۽ ها ته پرنٽ ڪندو ڇو ته هڪ سيٽ ۾ ٻه قدر هوندا هئا 0 ۽ 1 ۽ اسان انهن ٻنهي کي ڪ removedي ڇڏيو.

هر حرف بدلائڻ واري سوال کان پوءِ پالينروم کي چيڪ ڪرڻ لاءِ C ++ ڪوڊ

#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

جاوا ڪوڊ Palindrome کي چڪاس ڪرڻ لاءِ هر ڪردار جي متبادل واري سوال کان پوءِ

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) وقت وٺن ٿيون. وقت جي پيچيدگي لڪير ٿي ويندي آهي.

خلائي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان نقشي ۾ انپٽ تسلسل جا عنصر شامل ڪري رهيا آهيون. ۽ بدترين صورت ۾ ، اسان سڀني انڊيڪسز ۾ سڀني لاءِ غير مساوات وارا ڪردار ٿي سگهن ٿا. اهو اسان جي لاءِ او (اين) جي قيمت ڏيندو.