125. Valid Palindrome

week 1 number 5

مسئله: تشخیص تقارن کلمه (پالیندروم)

یک عبارت زمانی یک پالیندروم (متقارن) محسوب می‌شود که پس از تبدیل تمام حروف بزرگ به حروف کوچک و حذف تمام کاراکترهای غیر الفبایی و عددی (Alphanumeric)، خواندن آن از از هر طرف یکسان باشد. کاراکترهای Alphanumeric شامل حروف و اعداد هستند.

فرض کنید رشته‌ای به نام s به شما داده شده است. تابعی بنویسید که در صورت پالیندروم بودن s مقدار درست و در غیر این صورت مقدار نادرست را برگرداند.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

قیدها:

• 1 <= s.length <= 2 * 10^5
• s فقط از کاراکترهای اَسکی قابل چاپ تشکیل شده است.

راه‌حل۱: دو Pointer

از دو نشانگر i و j برای اشاره به دو انتهای رشته s استفاده می‌کنیم و سپس تا زمانی که i ≥ j فرآیند زیر را تکرار می‌کنیم:

۱. اگر s[i] حرف یا عدد نیست، نشانگر i را یک قدم به سمت راست حرکت دهید و به حلقه بعدی بروید.

۲. اگر s[j] حرف یا عدد نیست، نشانگر j را یک قدم به سمت چپ حرکت دهید و به حلقه بعدی بروید.

۳. اگر شکل حروف کوچک s[i] و s[j] برابر نباشند،  عبارت False  را برگردانید.

۴. در غیر این صورت، نشانگر i را یک قدم به راست و نشانگر j را یک قدم به چپ حرکت دهید و به حلقه بعدی بروید.

۵. در انتهای حلقه، مقدار True  را برگردانید.

پیچیدگی زمانی این الگوریتم O(n) است، که در آن O طول رشته s می‌باشد. پیچیدگی فضایی نیز برابر O(1) است.

func isPalindrome(s string) bool {
 i, j := 0, len(s)-1
 for i < j {
  if !isalnum(s[i]) {
   i++
  } else if !isalnum(s[j]) {
   j--
  } else if tolower(s[i]) != tolower(s[j]) {
   return false
  } else {
   i, j = i+1, j-1
  }
 }
 return true
}

func isalnum(ch byte) bool {
 return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}

func tolower(ch byte) byte {
 if ch >= 'A' && ch <= 'Z' {
  return ch + 32
 }
 return ch
}