קוק פֿאַר פּאַלינדראָמע נאָך יעדער אָנפֿרעג פון כאַראַקטער


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן facebook פליפּקאַרט גוגל Netflix
האַש שטריקל

די פּראָבלעם "טשעק פֿאַר פּאַלינדראָמע נאָך יעדער כאַראַקטער פאַרבייַט אָנפֿרעג" שטאַטן אַז רעכן איר באַקומען אַ שטריקל און ניט. פון פֿראגן, יעדער אָנפֿרעג האט צוויי ינטעגער אַרייַנשרייַב וואַלועס ווי i1 און i2 און איין כאַראַקטער ינפּוט גערופֿן 'טש'. די פּראָבלעם ויסזאָגונג צו טוישן די וואַלועס ביי i1 און i2 ינדיסעס מיט די געגעבן כאַראַקטער 'ch' און באַשליסן צי עס איז אַ פּאַלינדראָמע אָדער נישט.

באַמערקונג: 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: ענגליסע ווערט נאָך פאַרבייַט esglise

אָנפֿרעג 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. אַנדערש לייגן י 1 צו באַשטעטיק.
    3. איבערחזרן דעם פּראָצעס פֿאַר i2.
  4. איבערחזרן פֿון טרעטן 3 ביז די גאַנץ נומער פון פֿראגן געגעבן.
  5. אויב באַשטעטיק אויב ליידיק, עס איז פּאַלינדראָמע אַנדערש עס איז נישט.

דערקלערונג

מיר געבן אַ שטריקל און עטלעכע נומער פון פֿראגן, וואָס כּולל עטלעכע ינטאַדזשער וואַלועס און אותיות ינפּוט וואַלועס, מיר דאַרפֿן צו טוישן אָדער פאַרבייַטן די אותיות מיט די געגעבן כאַראַקטער און אין עטלעכע ינדיסעס וואָס זענען געגעבן ווי i1 און i2 און נאָך מיר דאַרפֿן צו באַשליסן אויב געשאפן שטריקל איז פּאַלינדראָמע אָדער ניט נאָך יעדער אָנפֿרעג געטאן. דער געדאַנק איז צו נוצן כאַשינג. מיר וועלן נוצן באַשטעטיקט צו סאָלווע דעם פּראָבלעם. מיר וועלן מאַכן באַזונדער פונקציאָנירן איין פֿונקציע איז צו נעמען פֿראגן און אן אנדער פֿונקציע איז צו קאָנטראָלירן פּאַלינדראָמע. בייסיקלי, די פֿונקציע אַרבעט אויף אַ ביסל ביי אַ ביסל מאָדע. ווייַל פון יעדער רופן מיר מאַכן דעם פֿונקציע. עס דורכפירן אַפּעריישאַנז אויף באַשטעטיקט און אין צוריקקער ווען מיר קאָנטראָלירן צי שטעלן איז ליידיק אָדער נישט. עס איז ליידיק, דאָס מיינט אַז די שטריקל איז אַ פּאַלינדראָמע, אַנדערש עס איז נישט.

לאָמיר באַטראַכטן אַ ביישפּיל:

בייַשפּיל

שטריקל: ינדיאַ, קווערי = 2, מיטל אַז עס וועט נעמען ינפּוץ פון י 1, י 2 און טש 2 מאל.

מיר דאַרפֿן צו קראָם די אַניקוואַל ינדעקסיז פון דער ערשטער העלפט פון שטריקל

נאָך דעם גאַנצן שטריקל, מיר וועלן באַשטעטיקן ווי דאָס,

שטעלן: [0, 1]

פֿאַר 1 אָנפֿרעג, i1 = 0, i2 = 4, ch = i, מיטל שטריקל "ינדיאַ" ווערט "indii".

i1 בלייבט i1 ווי 0, i2 ווערט 0, ערשט, i1 וועט דורכגיין און קאָנטראָלירן אויב str [i1] == str [n-1-i1] איז אויך פאָרשטעלן, אַזוי עס וועט באַזייַטיקן i1 מיטל 1 פון דעם גאַנג.

דעמאָלט 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 און מיר האָבן ביידע אַוועקגענומען.

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

Java קאָד צו טשעק פֿאַר פּאַלינדראָמע נאָך יעדער אָנפֿרעג פון כאַראַקטער

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (ק + ן) ווו "ק" איז די נומער פון פֿראגן און "N" איז די לענג פון די שטריקל. זינט ערשטער, מיר לויפן אַ שלייף ביז די האַלב-לענג פון די שטריקל און לייגן אַלע אַניקוואַל ינדאַסיז צו מאַפּע און דעמאָלט רעכענען די פֿראגן וואָס ינדיווידזשואַלי נעמען O (1) צייט. די צייט קאַמפּלעקסיטי ווערט לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (N), ווייַל מיר לייגן די יסודות פון די ינפּוט סיקוואַנס אין די מאַפּע. און אין די ערגסט פאַל, מיר קענען האָבן אַלע אַניקוואַל אותיות אין אַלע די ינדאַסיז. דאָס קאָס אונדז אַן O (N) פּלאַץ.