შეამოწმეთ Palindrome სიმბოლოების ყოველი ჩანაცვლების შემდეგ


Რთული ტური Hard
ხშირად ეკითხებიან Amazon Facebook Flipkart Google Netflix
Hash სიმებიანი

პრობლემა "შეამოწმეთ პალინდრომი სიმბოლოების ყოველი ჩანაცვლების შემდეგ" აცხადებს, რომ თქვენ გეძლევათ ა სიმებიანი და არა. მოთხოვნების მიხედვით, თითოეულ მოთხოვნას აქვს ორი მთელი რიცხვი შეყვანის მნიშვნელობები, როგორც i1 და i2 და ერთი პერსონაჟის შეყვანა სახელწოდებით "ch" პრობლემის დებულება ითხოვს შეცვალოს მნიშვნელობები i1 და i2 ინდექსებში მოცემული სიმბოლოთი 'ch' და განსაზღვროს არის ის პალინდრომი თუ არა.

შენიშვნა: 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: ინდოეთი ხდება ჩანაცვლების შემდეგ indii

მოთხოვნა 2: indi ხდება indni ჩანაცვლების შემდეგ

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: englise ხდება ჩანაცვლების esglise შემდეგ

შეკითხვა 3: esglise ხდება ჩანაცვლების შემდეგ

ალგორითმი

  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 Set- ს.
    3. გაიმეორეთ ეს პროცესი i2– ისთვისაც.
  4. გაიმეორეთ ნაბიჯი 3-დან მოცემული მოთხოვნების საერთო რაოდენობამდე.
  5. თუ უცნობია თუ ცარიელია, მაშინ პალინდრომია, ეს ასე არ არის.

განმარტება

ჩვენ მოგვცეს სტრიქონი და რამდენიმე რაოდენობის მოთხოვნა, რომელიც შეიცავს მასში მთელი რიცხვისა და სიმბოლოების შეტანას, ჩვენ უნდა შევცვალოთ ან შეცვალოთ სიმბოლოები მოცემული სიმბოლოთი და გარკვეული ინდექსებით, რომლებიც მოცემულია i1 და i2 და შემდეგ დაგვჭირდება იმის დასადგენად, ჩამოყალიბებული სტრიქონი არის პალინდრომი თუ არა ყოველი შეკითხვის შესრულების შემდეგ. იდეა არის გამოიყენოს ჰასინგი. ჩვენ ვაყენებთ Set- ს გამოყენებას ამ პრობლემის მოსაგვარებლად. ჩვენ ვაპირებთ განვახორციელოთ ცალკე ფუნქცია, ერთი ფუნქციაა მოთხოვნების მიღება და სხვა ფუნქციაა პალინდრომის შემოწმება. ძირითადად, ეს ფუნქცია მუშაობს ცოტათი ცოტათი. თითოეული ზარის გამო, ჩვენ ვხდებით ამ ფუნქციას. იგი ასრულებს ოპერაციებს Set– ზე და სამაგიეროდ, როდესაც ვამოწმებთ, ცარიელია თუ არა Set. ეს ცარიელია, ეს ნიშნავს, რომ სტრიქონი არის პალინდრომი, სხვაგვარად ეს ასე არ არის.

განვიხილოთ მაგალითი:

მაგალითი

სტრიქონი: ინდოეთი, მოთხოვნა = 2, ნიშნავს რომ ის მიიღებს i1, i2 და ch შენატანებს 2-ჯერ.

ჩვენ უნდა შევინახოთ სიმების პირველი ნახევრის არათანაბარი ინდექსები

მთლიანი სტრიქონის გადაკვეთის შემდეგ, ჩვენ გვექნება ასე Set,

დაყენება: [0, 1]

I შეკითხვისთვის, 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 არის, ასე რომ არაფერი მოხდება.

მე -2 მოთხოვნისთვის, i1 = 1, i2 = 3, ch = n, ნიშნავს, რომ ”indii” ხდება ”indni”.

i1 რჩება i1 როგორც 1, i2 ხდება 1, პირველი, i1 გაივლის და შეამოწმებს, არის თუ არა str [i1] == str [n-1-i1], მართალია, შემდეგ შეამოწმებს, i1 არის თუ არა ნაკრებში, ეს ასევე არსებობს, ასე რომ, იგი ამოიღებს i1 საშუალებებს 1 ნაკრებიდან. შემდეგ ყველა მოთხოვნის შესრულების შემდეგ შეამოწმებს არის თუ არა Set ცარიელი და ახლა ცარიელია და ის დაბეჭდავს დიახ, რადგან ნაკრებში იყო ორი და 0 მნიშვნელობა და ჩვენ ორივე ამოვიღეთ.

C ++ კოდი, რათა შეამოწმოთ Palindrome სიმბოლოების ყოველი ჩანაცვლების შემდეგ

#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

სირთულის ანალიზი

დროის სირთულე

O (Q + N) სადაც "Q" არის შეკითხვების რაოდენობა და "N" სიმების სიგრძეა. მას შემდეგ, რაც პირველ რიგში, ჩვენ ვაწარმოებთ ციკლს სიმების ნახევარ სიგრძემდე და დავამატებთ ყველა უთანასწორო ინდექსს რუქაზე და შემდეგ გამოვთვალოთ მოთხოვნები, რომლებიც ინდივიდუალურად იღებს O (1) დროს. დროის სირთულე ხაზოვანი ხდება.

სივრცის სირთულე

O (N), რადგან ჩვენ შევსების თანმიმდევრობის ელემენტებს ვუმატებთ რუქას. და უარეს შემთხვევაში, ჩვენ შეგვიძლია ყველა არათანაბარი სიმბოლო გვქონდეს ყველა ინდექსში. ეს დაგვიჯდება O (N) სივრცე.