Палиндромын дэд сүлжээний асуултууд  


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны БайтДанс Ebay Expedia Google-ийн Intuit Microsoft- PayPal Pinterest Синопсис
Динамик програмчлал Хаширч байна Асуулгын асуудал String

Асуудлын мэдэгдэл  

"Палиндромын дэд мөрийн лавлагаа" гэсэн асуудалд танд String болон зарим асуултыг өгсөн гэж заасан байдаг. Эдгээр асуултуудын дагуу та уг асуулгаас үүссэн дэд мөр нь палиндром мөн үү үгүй ​​юу гэдгийг тодорхойлох ёстой.

Жишээ нь  

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] нь палиндром бөгөөд үр дүн нь YES болно. Дэд мөр нь “abbabba” юм.

арга барил  

Асуулга бүр дээр үндэслэн бид String болон зарим асуултуудыг өгсөн. Бид байгуулагдсан дэд мөрийг тодорхойлох ёстой палиндром эсвэл биш. String ашиглах Хаширч байна үүнийг шийдэх. Бид хоёр массивыг анхны мөрөнд, нөгөө мөрийг буцаах мөрөнд ашиглах болно. Дараа нь бид String-ийн хэш утгыг хадгалах болно. Энд Hash Value нь нөгөөгөөсөө өөр байж болно. Бид Hring Value-ийг String [] -р, харин Reverse String-ийг Hash Value-г авч байна гэж бодъё. Бид угтвар ба дагавар массивыг авах болно.

Бид String str гэж бодъё: “aabbbababaaa”.

Бид str as-ийн хэш утгыг хадгалах болно

Угтвар [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 шийдэл

Одоо та нарын олонхи нь яагаад ийм маягаар Hash Values-ийг хадгалах арга зам гэж бодож байна. Хариулт нь хамгийн бага хугацааны төвөгтэй энгийн томъёог ашиглан дурын өгөгдсөн мөрийн хэшийн утгыг хайх арга юм.

Хэш утга (Зүүн, Баруун) = угтвар [Баруун + 1] - угтвар [Зүүн].

Зүүн ба баруун нь мөрийн эхлэлийн цэг байж болно, хэрвээ бид мөрний хэш утгыг олохыг хүсвэл (2, 4) = “bbb” бол ердөө л дараах байдалтай байна.

угтвар [5] - угтвар [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

Энэ утга нь палиндромыг олоход тусална. Учир нь бид дагаврын массивыг мөн адил хийх болно, гэхдээ энэ удаад хэрхэн яаж хийхийг үзье.

String 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.

Одоо бид урвуу Хэшийн утгыг дараахь байдлаар тооцоолж болно.

Урвуу хэшийн утга (Зүүн, Баруун): Хэш утга (Баруун, Зүүн) = дагавар [n-Зүүн] - дагавар [n-Баруун-1].

Жишээ нь

Жишээлбэл: String str: “aabbbababaaa”.

Урвуу хэшийн утга: дэд мөр (2,4):

“Bbba” -ийн утгыг буцаах нь “abbb”

Дагавар [11-1] - дагавар [11-4-1] = дагавар [10] -хэвтэр [6].

Одоо палиндром байгаа эсэхийг олж мэдэх тэгшитгэл бидэнд байна.

Одоо бид угтвар, дагавар гэсэн хоёр массивтай болж, хоорондоо хамааралтай болсон.

(угтвар [Баруун + 1] - угтвар [Зүүн])  =  (дагавар [n - Зүүн] - дагавар [n - Баруун- 1])

мөн үзнэ үү
Одоогийн тооны Leetcode шийдлээс хэдэн тоо бага байна

(101Зүүн талд) (101n - Баруун - 1)

 

Палиндромын дэд сүлжээний асуултуудPin  

код  

Palindrome Substring Queries-д зориулсан C ++ код

#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

Palindrome Substring Queries-ийн Java код

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) цагт хариулах тул алгоритм нь цаг хугацааны шугаман нарийн төвөгтэй байдаг.

мөн үзнэ үү
Өгөгдсөн нийлбэр бүхий дэд массивыг олох (Сөрөг тоотой харьцах)

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" гэдэг нь өгөгдсөн мөр дэх тэмдэгтийн тоо юм. Бид мөрөнд хэш утгыг хадгалсан тул. Бид нэмэлт зай ашигласан.