242. Valid Anagram

مسئله:

فرض کنید دو رشته s و t به شما داده شده است. تابعی بنویسید که در صورت آناگرام بودن t نسبت به s مقدار true و در غیر این صورت مقدار false را برگرداند.

آناگرام: کلمه یا عبارتی است که با بازآرایی حروف یک کلمه یا عبارت دیگر و استفاده از تمام حروف اصلی فقط یک بار تشکیل می‌شود.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

محدودیت‌ها:

• طول دو رشته s و t بین ۱ تا ۵۰۰۰۰ است.
• رشته‌های s و t فقط شامل حروف کوچک انگلیسی هستند.

راه‌حل : شمارش (Counting)

ابتدا بررسی می‌کنیم که آیا طول دو رشته برابر است یا خیر. اگر طول دو رشته با هم برابر نباشد، به این معنی است که کاراکترهای موجود در آن‌ها متفاوت هستند، بنابراین false را برمی‌گردانیم.

در غیر این صورت، از یک جدول hash یا یک آرایه به طول ۲۶ (به تعداد حروف انگلیسی) برای ثبت تعداد دفعات ظهور هر کاراکتر در رشته s استفاده می‌کنیم و سپس رشته دیگر t را پیمایش می‌کنیم. هر بار که روی یک کاراکتر پیمایش می‌کنیم، تعداد دفعات ظهور کاراکتر مربوطه در جدول hash را یک واحد کم می‌کنیم. اگر تعداد بعد از کم کردن کمتر از ۰ شود، به این معنی است که تعداد دفعات ظهور کاراکتر در دو رشته متفاوت است، بنابراین false را برمی‌گردانیم. اگر پس از پیمایش هر دو رشته، تمام شمارش کاراکترها در جدول hash برابر با ۰ باشد، به این معنی است که کاراکترها در دو رشته تعداد دفعات برابری ظاهر شده‌اند، بنابراین true را برمی‌گردانیم.

پیچیدگی زمانی این الگوریتم O(n) است، پیچیدگی فضایی نیز O(c) می‌باشد، که در آن n طول رشته و c اندازه مجموعه کاراکترها (در این مسئله برابر با ۲۶ یعنی برابر اب تعداد حروف انگلیسی است).

func isAnagram(s string, t string) bool {
 if len(s) != len(t) {
  return false
 }
 cnt := [26]int{}
 for i := 0; i < len(s); i++ {
  cnt[s[i]-'a']++
  cnt[t[i]-'a']--
 }
 for _, v := range cnt {
  if v != 0 {
   return false
  }
 }
 return true
}