ກວດສອບ Palindrome ຫຼັງຈາກທຸກໆ Query ທົດແທນຕົວອັກສອນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ເຟສບຸກ Flipkart ກູໂກ Netflix
Hash string

ບັນຫາ "ກວດສອບ Palindrome ຫຼັງຈາກທຸກໆ ຄຳ ຖາມປ່ຽນແທນຕົວອັກສອນ" ລະບຸວ່າເຈົ້າຄິດວ່າເຈົ້າຖືກກ string ແລະບໍ່. ຂອງການສອບຖາມ, ແຕ່ລະ ຄຳ ຖາມມີສອງອັນ integer ມູນຄ່າການປ້ອນຂໍ້ມູນເປັນ i1 ແລະ i2 ແລະການປ້ອນຂໍ້ມູນຕົວອັກສອນ ໜຶ່ງ ຊື່ວ່າ 'ch'. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ປ່ຽນຄ່າທີ່ i1 ແລະ i2 ຕົວຊີ້ວັດກັບຕົວອັກສອນທີ່ໃຫ້ 'ch' ແລະ ກຳ ນົດວ່າມັນເປັນ palindrome ຫຼືບໍ່.

ໝາຍ ເຫດ: 0 <ແມ່ນນ້ອຍກວ່າຫລືເທົ່າກັບ i1 ແລະ i2 ໜ້ອຍ ກວ່າຫລືເທົ່າກັບຄວາມຍາວຂອງສາຍ.

ຍົກຕົວຢ່າງ

ກວດສອບ Palindrome ຫຼັງຈາກທຸກໆ Query ທົດແທນຕົວອັກສອນ

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: indii ກາຍເປັນຫລັງການປ່ຽນແທນ

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: ພາສາອັງກິດກາຍເປັນພາສາອັງກິດຫລັງຈາກທົດແທນ englise

ການສອບຖາມທີ 2: ການລອກລຽນກາຍເປັນຫຼັງຈາກການທົດແທນ esglise

ການສອບຖາມ 3: esglise ຈະກາຍເປັນຫຼັງຈາກການທົດແທນ esilise

ລະບົບວິເຄາະ

  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. ຖ້າຕັ້ງຖ້າວ່າງຫວ່າງແລ້ວມັນກໍ່ແມ່ນ palindrome ອີກອັນ ໜຶ່ງ ມັນບໍ່ແມ່ນ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ String ແລະບາງ ຄຳ ຖາມ, ເຊິ່ງປະກອບດ້ວຍຄຸນຄ່າຂອງຕົວເລກບວກແລະຕົວອັກສອນບາງຢ່າງໃນນັ້ນ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງປ່ຽນຫລືປ່ຽນຕົວອັກສອນດ້ວຍຕົວອັກສອນທີ່ໃຫ້ໄວ້ແລະໃນຕົວຊີ້ວັດບາງຢ່າງທີ່ໃຫ້ເປັນ i1 ແລະ i2 ແລະຫຼັງຈາກນັ້ນພວກເຮົາຕ້ອງການ ເພື່ອ ກຳ ນົດວ່າເຊືອກທີ່ຖືກສ້າງຕັ້ງຂື້ນແມ່ນ palindrome ຫຼືບໍ່ຫຼັງຈາກການສອບຖາມແຕ່ລະອັນ. ແນວຄວາມຄິດແມ່ນການ ນຳ ໃຊ້ ເຮື້ອຮັງ. ພວກເຮົາຈະໃຊ້ຊຸດເພື່ອແກ້ໄຂບັນຫານີ້. ພວກເຮົາ ກຳ ລັງຈະເຮັດ ໜ້າ ທີ່ແຍກຕ່າງຫາກ ໜຶ່ງ ໜ້າ ທີ່ຄືການສອບຖາມແລະອີກ ໜ້າ ທີ່ ໜຶ່ງ ແມ່ນກວດສອບ palindrome. ໂດຍພື້ນຖານແລ້ວ, ຟັງຊັນນັ້ນຈະເຮັດວຽກແບບເລັກໆນ້ອຍໆ. ຍ້ອນການໂທແຕ່ລະອັນພວກເຮົາເຮັດ ໜ້າ ທີ່ນັ້ນ. ມັນປະຕິບັດການ ດຳ ເນີນງານກ່ຽວກັບ Set ແລະໃນການກັບມາເມື່ອພວກເຮົາກວດເບິ່ງວ່າ Set ແມ່ນຫວ່າງຫລືບໍ່. ມັນແມ່ນຫວ່າງເປົ່າມັນຫມາຍຄວາມວ່າຊ່ອຍແນ່ແມ່ນ palindrome, ອື່ນມັນບໍ່ແມ່ນ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

ສະຕິງ: ອິນເດຍ, ສອບຖາມ = 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 ຈາກຊຸດ. ຫຼັງຈາກນັ້ນ, ຫຼັງຈາກການສອບຖາມທັງ ໝົດ ໄດ້ປະຕິບັດມັນຈະກວດເບິ່ງວ່າ Set ແມ່ນຫວ່າງແລ້ວແລະດຽວນີ້ມັນຫວ່າງແລ້ວແລະມັນຈະພິມແມ່ນຍ້ອນວ່າໃນຊຸດໃດ ໜຶ່ງ ມັນມີສອງຄ່າ 0 ແລະ 1 ແລະພວກເຮົາເອົາທັງສອງຂໍ້ນີ້ອອກ.

ລະຫັດ 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

ລະຫັດ Java ເພື່ອກວດສອບ Palindrome ຫຼັງຈາກທຸກໆ Query ທົດແທນຕົວອັກສອນ

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) ບ່ອນທີ່ "ຖາມ" ແມ່ນ ຈຳ ນວນ ຄຳ ຖາມແລະ "N" ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່. ນັບຕັ້ງແຕ່ ທຳ ອິດພວກເຮົາ ດຳ ເນີນການ loop ຈົນເຖິງຄວາມຍາວເຄິ່ງ ໜຶ່ງ ຂອງ string ແລະເພີ່ມຕົວຊີ້ບອກທີ່ບໍ່ເທົ່າກັນທັງ ໝົດ ເຂົ້າໃນແຜນທີ່ແລະຫຼັງຈາກນັ້ນລວບລວມ ຄຳ ຖາມທີ່ໃຊ້ເວລາ O (1) ເປັນສ່ວນບຸກຄົນ. ຄວາມສັບສົນຂອງເວລາກາຍເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເພາະວ່າພວກເຮົາ ກຳ ລັງເພີ່ມສ່ວນປະກອບຂອງ ລຳ ດັບການປ້ອນຂໍ້ມູນເຂົ້າໃນແຜນທີ່. ແລະໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາສາມາດມີຕົວອັກສອນທີ່ບໍ່ເທົ່າກັນທັງ ໝົດ ຢູ່ໃນຕົວຊີ້ວັດທັງ ໝົດ. ນີ້ຈະເຮັດໃຫ້ພວກເຮົາມີຊ່ອງ O (N).