แบบสอบถามสตริงย่อย Palindrome  


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน ByteDance อีเบย์ Expedia Google ตรัสรู้ ไมโครซอฟท์ บัตรเครดิต/เดบิต หรือ PayPal Pinterest Synopsys
การเขียนโปรแกรมแบบไดนามิก hashing ปัญหาการสืบค้น เชือก

คำชี้แจงปัญหา  

ปัญหา“ Palindrome Substring Queries” ระบุว่าคุณได้รับสตริงและข้อความค้นหาบางอย่าง ด้วยคำค้นหาเหล่านั้นคุณต้องพิจารณาว่าสตริงย่อยที่สร้างขึ้นจากคิวรีนั้นเป็นพาลินโดรมหรือไม่

ตัวอย่าง  

String str = "aaabbabbaaa"

Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} }
The Substring [2 3] is not a palindrome

The Substring [2 8] is a palindrome

The Substring [5 7] is not a palindrome

The Substring [3 7] is a palindrome

คำอธิบาย: สตริงย่อย [2,8] เป็นพาลินโดรมดังนั้นผลลัพธ์จึงเป็นใช่ สตริงย่อยคือ "Abbabba"

เข้าใกล้  

เราได้ให้สตริงและข้อความค้นหาบางส่วนตามแต่ละคำค้นหา เราต้องกำหนดสตริงย่อยที่เกิดขึ้นจึงเป็นไฟล์ palindrome หรือไม่. ใช้ String hashing เพื่อแก้ปัญหานี้ เราจะใช้สองอาร์เรย์หนึ่งสำหรับสตริงเดิมและอีกหนึ่งสำหรับสตริงที่กลับด้าน จากนั้นเราจะจัดเก็บค่าแฮชของ String ที่นี่ค่าแฮชอาจแตกต่างจากที่อื่น สมมติว่าเรากำลังใช้ค่า Hash สำหรับ String [] และค่า Hash ย้อนกลับสำหรับ String ที่กลับรายการ เราจะใช้อาร์เรย์คำนำหน้าและคำต่อท้าย

สมมติว่าเรามี String str:“ aabbbababaaa”

เราจะจัดเก็บค่าแฮชของ str เป็น

คำนำหน้า [i] = str [0] + str [1] * 101 + str [2] * 1012  + ………. + str [i-1] * 101 *I-1  .

สำหรับแต่ละค่าของคำนำหน้า [i] เราจะมีค่าต่างๆดังนี้

Prefix[0]=0,
Prefix[1]= 97 + 97 *101, ( 0+ ASCII value of a)
Prefix[2]= 97 + 97 *101 + 98 *101^2
Prefix[3]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
Prefix [12]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 +…… +97 *101^11 as length of String is 12.

 

ดูสิ่งนี้ด้วย
เวลาขั้นต่ำในการเยี่ยมชมทุกจุด Leetcode Solution

ตอนนี้หลาย ๆ ท่านกำลังคิดว่าทำไมจึงเป็นวิธีการจัดเก็บค่าแฮชในลักษณะนี้ คำตอบคือวิธีค้นหาค่าแฮชของสตริงย่อยที่กำหนดโดยใช้สูตรง่ายๆในเวลาที่ซับซ้อนน้อยที่สุด

ค่าแฮช (ซ้ายขวา) = คำนำหน้า [ขวา + 1] - คำนำหน้า [ซ้าย]

ซ้ายและขวาสามารถเป็นจุดเริ่มต้นของสตริงย่อยได้หากเราต้องการหาค่าแฮชของสตริง (2, 4) =“ bbb” ก็จะเป็น:

คำนำหน้า [5] - คำนำหน้า [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

ค่านี้จะช่วยในการค้นหาพาลินโดรม เพราะเช่นเดียวกับที่เราจะทำกับอาร์เรย์ต่อท้าย แต่คราวนี้จากที่แล้วมาดูกันว่า

สตริง str:“ aabbbababaaa”

suffix[i] = str[n-1]+ str[n-2] *101 + str[n-3]*1022  + ……….+ str[n-i]*101*i-1  .
suffix[0]=0,
suffix [1]= 97 + 97 *101, ( 0+ ASCII value of a)
suffix [2]= 97 + 97 *101 + 97 *101^2,
suffix [3]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
.
suffix [11]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 +…… +97 *101^10 as length of String is 11.

ตอนนี้เราสามารถคำนวณมูลค่าของ Reverse Hash Value โดยใช้:

Reverse Hash Value (ซ้าย, ขวา): ค่าแฮช (ขวา, ซ้าย) = คำต่อท้าย [n-Left] - คำต่อท้าย [n-Right-1]

ตัวอย่าง

ตัวอย่างเช่น String str:“ aabbbababaaa”

ค่าแฮชย้อนกลับ: สตริงย่อย (2,4):

การกลับค่าของ“ bbba” คือ“ abbb”

คำต่อท้าย [11-1] - คำต่อท้าย [11-4-1] = คำต่อท้าย [10] -suffix [6]

และตอนนี้เรามีสมการที่จะหาพาลินโดรมว่ามีอยู่จริงหรือไม่

ตอนนี้เรามีสองอาร์เรย์เป็นคำนำหน้าและคำต่อท้ายเรามีความสัมพันธ์ระหว่างกัน

(คำนำหน้า [ขวา + 1] - คำนำหน้า [ซ้าย])  =  (คำต่อท้าย [n - ซ้าย] - คำต่อท้าย [n - ขวา - 1])

ดูสิ่งนี้ด้วย
จำนวนตัวเลขที่เล็กกว่าโซลูชัน Leetcode จำนวนปัจจุบัน

(101ซ้าย) (101n - ขวา - 1)

 

แบบสอบถามสตริงย่อย Palindromeหมุด  

รหัส  

รหัส C ++ สำหรับ Palindrome Substring Queries

#include<iostream>

using namespace std;

#define p 101
#define MOD 1000000007

struct Queries
{
    int left, right;
};
bool CheckPalindrome(string str, int left, int right)
{
    while (right > left)
        if (str[left++] != str[right--])
            return (false);
    return (true);
}
unsigned long long int moduloPower(unsigned long long int base,unsigned long long int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    unsigned long long int temp = moduloPower(base, exponent / 2);

    if (exponent % 2 == 0)
        return (temp % MOD * temp % MOD) % MOD;
    else
        return (((temp % MOD * temp % MOD) % MOD)* base % MOD)% MOD;
}

unsigned long long int ModuloMultiplicativeInverse(unsigned long long int n)
{
    return moduloPower(n, MOD - 2);
}

void HashPrefix( string str, int n, unsigned long long int prefix[], unsigned long long int powerArr[])
{
    prefix[0] = 0;
    prefix[1] = str[0];

    for (int i = 2; i <= n; i++)
        prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;

    return;
}

void HashSuffix( string str, int n, unsigned long long int suffix[], unsigned long long int powerArr[])
{
    suffix[0] = 0;
    suffix[1] = str[n - 1];

    for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        suffix[j] = (suffix[j - 1] % MOD+ (str[i] % MOD* powerArr[j - 1] % MOD)% MOD)% MOD;

    return;
}
void GetQueryOutput(string str, Queries q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int powerArr[])
{
    for (int i = 0; i <= m - 1; i++)
    {
        int left = q[i].left;
        int right = q[i].right;

        unsigned long long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

        unsigned long long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

        if (HashValue == reverseHashValue)
        {
            if (CheckPalindrome(str, left, right) == true)
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
            else
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
        }

        else
            cout<<"The Substring ["<< left <<" "<<right<<"] is not a palindrome\n";
    }

    return;
}
void assginedPowers(unsigned long long int powerArr[], int n)
{
    powerArr[0] = 1;

    for (int i = 1; i <= n; i++)
        powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

    return;
}
int main()
{
    string str = "aaabbabbaaa";
    int n = str.length();

    unsigned long long int powerArr[n + 1];

    assginedPowers(powerArr, n);

    unsigned long long int prefix[n + 1];
    unsigned long long int suffix[n + 1];

    HashPrefix(str, n, prefix, powerArr);
    HashSuffix(str, n, suffix, powerArr);

    Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} };
    int m = sizeof(q) / sizeof(q[0]);

    GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    return (0);
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

โค้ด Java สำหรับ Palindrome Substring Queries

public class PalindromeSubstringQuery
{
    static int p = 101;
    static int MOD = 1000000007;

    public static class Queries
    {
        int left, right;
        public Queries(int left, int right)
        {
            this.left = left;
            this.right = right;
        }
    }
    public static boolean CheckPalindrome(String str, int left, int right)
    {
        while (right > left)
        {
            if (str.charAt(left++) != str.charAt(right--))
                return (false);
        }
        return (true);
    }
    public static int moduloPower(int base, int exponent)
    {
        if (exponent == 0)
        {
            return 1;
        }
        if (exponent == 1)
        {
            return base;
        }
        int temp = moduloPower(base, exponent / 2);

        if (exponent % 2 == 0)
        {
            return (temp % MOD * temp % MOD) % MOD;
        }
        else
        {
            return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;
        }
    }
    public static int ModuloMultiplicativeInverse(int n)
    {
        return moduloPower(n, MOD - 2);
    }

    public static void HashPrefix(String str, int n,int prefix[], int powerArr[])
    {
        prefix[0] = 0;
        prefix[1] = str.charAt(0);

        for (int i = 2; i <= n; i++)
        {
            prefix[i] = (prefix[i - 1] % MOD+ (str.charAt(i - 1) % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
        }
        return;
    }
    public static void HashSuffix(String str, int n,int suffix[], int powerArr[])
    {
        suffix[0] = 0;
        suffix[1] = str.charAt(n - 1);

        for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        {
            suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD* powerArr[j - 1] % MOD) 	% MOD) % MOD;
        }
        return;
    }
    public static void GetQueryOutput( String str, Queries q[], int m, int n, int prefix[], int suffix[], int powerArr[])
    {
        for (int i = 0; i <= m - 1; i++)
        {
            int left = q[i].left;
            int right = q[i].right;

            long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

            long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

            if (HashValue == reverseHashValue)
            {
                if (CheckPalindrome(str, left, right) == true)
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is a palindrome\n");
                }
                else
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
                }
            }
            else
            {
                System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
            }
        }
        return;
    }
    public static void assginedPowers(int powerArr[], int n)
    {
        powerArr[0] = 1;

        for (int i = 1; i <= n; i++)
            powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

        return;
    }
    public static void main(String[] args)
    {
        String str = "aaabbabbaaa";
        int n = str.length();

        int[] powerArr = new int[n + 1];

        assginedPowers(powerArr, n);

        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];

        HashPrefix(str, n, prefix, powerArr);
        HashSuffix(str, n, suffix, powerArr);

        Queries q[] = { new Queries(2, 3), new Queries(2, 8),new Queries(5, 7), new Queries(3, 7) };

        int m = q.length;

        GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    }
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

O (N + Q) ที่ไหน “ N” คือขนาดของสตริงและ "Q" คือจำนวนแบบสอบถามที่ต้องดำเนินการ ดังนั้นอัลกอริทึมจึงมีความซับซ้อนของเวลาเชิงเส้นเมื่อเราตอบคำถามแต่ละข้อในเวลา O (1)

ดูสิ่งนี้ด้วย
ค้นหา subarray ด้วยผลรวมที่กำหนด (จัดการกับ Negative Numbers)

ความซับซ้อนของอวกาศ

บน) ที่ไหน “ N” คือจำนวนอักขระในสตริงที่กำหนด เนื่องจากเราได้เก็บค่าแฮชสำหรับสตริง เราใช้พื้นที่พิเศษ