مراقبه های LeetCode: زیر رشته های پالیندرومیک – انجمن DEV

توضیحات زیر رشته های پالیندرومیک به شرح زیر است:

یک رشته داده شده است s، برگشت تعداد زیر رشته های پالیندرومیک در آن.

یک رشته یک است پالیندروم زمانی که همان عقب و جلو خوانده می شود.

آ رشته فرعی یک دنباله به هم پیوسته از کاراکترهای درون رشته است.

مثلا:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

یا:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

همچنین، محدودیت ها نشان می دهد که s از حروف کوچک انگلیسی تشکیل شده است.

در مسئله قبلی، راه حلی برای یافتن طولانی ترین زیررشته پالیندرومیک در یک رشته معین پیدا کردیم. برای یافتن یک پالیندروم، از رویکرد “بسط بر روی مرکز” استفاده کردیم، که در آن هر کاراکتر را به عنوان کاراکتر میانی یک زیر رشته در نظر گرفتیم. و بر این اساس، نشانگرهای چپ و راست را جابجا کردیم.

شمارش پالیندروم ها در یک رشته فرعی ممکن است به شکل زیر باشد:

function countPalindromesInSubstr(s: string, left: number, right: number): number {
  let result = 0;
  while (left >= 0 && right  s.length && s[left] === s[right]) {
    result++;
    left--;
    right++;
  }

  return result;
}

تا زمانی که در محدوده هستیم (left >= 0 && right ), we check if two characters on the left and right are the same — if so, we update our result و نشانگرهای ما را جابجا کنیم.

با این حال، هنگامی که در مورد آن فکر می کنید، مهم است که نشانگرها در کدام شاخص ها مقداردهی اولیه می شوند. مثلاً اگر رشته را پاس کنیم "abc" به countPalindromesInSubstr، و left اشاره گر در است 0 در حالی که right نشانگر در آخرین نمایه است (2، سپس نتیجه ما به سادگی است 0.

به یاد داشته باشید که ما هر کاراکتر را به عنوان کاراکتر میانی یک زیررشته فرض می کنیم، و از آنجایی که هر کاراکتر منفرد نیز یک رشته فرعی است، نشانگرهای چپ و راست خود را برای اشاره به خود کاراکتر مقداردهی اولیه می کنیم.

بیایید ببینیم این فرآیند چگونه ممکن است به نظر برسد.

اگر رشته را داشته باشیم "abc"، ابتدا این را فرض می کنیم 'a' وسط یک زیر رشته است:

"abc"

left = 0
right = 0
currentSubstr="a"

totalPalindromes = 1 // A single character is a palindrome

سپس، ما سعی خواهیم کرد رشته فرعی را گسترش دهیم تا ببینیم آیا 'a' می تواند کاراکتر میانی یک زیررشته دیگر باشد:

"abc"

left = -1
right = 1
currentSubstr = undefined

totalPalindromes = 1

حالا که ما left اشاره گر خارج از محدوده است، می توانیم به کاراکتر بعدی برویم:

"abc"

left = 1
right = 1
currentSubstr="b"

totalPalindromes = 2

اکنون، ما نشانگرهای خود را به روز می کنیم، و در واقع، 'b' می تواند کاراکتر میانی یک زیررشته دیگر باشد:

s = "abc"

left = 0
right = 2
currentSubstr="abc"

totalPalindromes = 2

خوب، currentSubstr پالیندروم نیست اکنون اشاره گرهای خود را دوباره به روز می کنیم:

s = "abc"

left = -1
right = 3
currentSubstr = undefined

totalPalindromes = 2

و ما دوباره از محدوده خارج شدیم. زمان رفتن به شخصیت بعدی:

s = "abc"

left = 2
right = 2
currentSubstr="c"

totalPalindromes = 3

با جابجایی نشانگرهایمان، دوباره از محدوده خارج خواهیم شد:

s = "abc"

left = 1
right = 3
currentSubstr = undefined

totalPalindromes = 3

اکنون که ما از طریق هر شخصیت رفته ایم، نتیجه نهایی ما از totalPalindromes است، در این مورد، 3. به این معنی که وجود دارد 3 زیر رشته های پالیندرومیک در "abc".

با این حال، یک هشدار مهم وجود دارد: هر بار که یک کاراکتر را وسط فرض می کنیم و دو نشانگر را در سمت چپ و راست آن مقداردهی اولیه می کنیم، سعی می کنیم فقط پالیندروم هایی با طول فرد پیدا کنیم. برای کاهش آن، به جای در نظر گرفتن یک کاراکتر به عنوان وسط، می توانیم دو کاراکتر را وسط در نظر بگیریم و مانند قبل گسترش دهیم.

در این مورد، فرآیند یافتن پالیندروم‌های زیر رشته‌ای با طول زوج به این شکل خواهد بود – در ابتدا، ما right اشاره گر است left + 1:

s = "abc"

left = 0
right = 1
currentSubstr="ab"

totalPalindromes = 0

سپس، ما نشانگرهای خود را به روز می کنیم:

s = "abc"

left = -1
right = 2
currentSubstr = undefined

totalPalindromes = 0

خارج از محدوده. برو به شخصیت بعدی:

s = "abc"

left = 1
right = 2
currentSubstr="bc"

totalPalindromes = 0

به روز رسانی اشاره گرهای ما:

s = "abc"

left = 0
right = 3
currentSubstr = undefined

totalPalindromes = 0

این right اشاره گر خارج از محدوده است، بنابراین به کاراکتر بعدی می رویم:

s = "abc"

left = 2
right = 3
currentSubstr = undefined

totalPalindromes = 0

یک بار دیگر ما از محدوده خارج شده ایم و بررسی هر شخصیت را تمام کرده ایم. در این مثال هیچ پالیندرومی برای زیررشته‌های با طول زوج وجود ندارد.

می‌توانیم تابعی بنویسیم که کار شمارش پالیندروم‌های هر زیر رشته را انجام می‌دهد:

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i  s.length; i++) {
    let left = i;
    let right = isOddLength ? i : i + 1;
    result += countPalindromesInSubstr(s, left, right);
  }

  return result;
}

در تابع اصلی ما می توانیم تماس بگیریم countPalindromes دو بار برای هر دو رشته فرعی با طول فرد و زوج و برگردانید result:

function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

به طور کلی راه حل ما به این صورت است:

function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i  s.length; i++) {
    let left = i;
    let right = isOddLength ? i : i + 1;
    result += countPalindromesInSubstr(s, left, right);
  }

  return result;
}

function countPalindromesInSubstr(s: string, left: number, right: number): number {
  let result = 0;
  while (left >= 0 && right  s.length && s[left] === s[right]) {
    result++;
    left--;
    right++;
  }

  return result;
}

پیچیدگی زمان و مکان

پیچیدگی زمانی است

$O(n^2)$

همانطور که از هر زیر رشته برای هر کاراکتر عبور می کنیم (countPalindromes در حال انجام است

$O(n^2)$

عملیات، ما آن را دو بار صدا می زنیم بصورت جداگانه.)
پیچیدگی فضا است

$O (1)$

زیرا ما یک ساختار داده اضافی نداریم که اندازه آن با اندازه ورودی افزایش می یابد.

در مرحله بعد مشکلی به نام روش های رمزگشایی است. تا آن زمان، کد نویسی مبارک.