20. Valid Parentheses

مسئله Valid Parentheses:

فرض کنید رشته‌ای از کاراکترها به نام s دارید که فقط شامل موارد زیر است:

• ( -(پرانتز باز)
• ) - (پرانتز بسته)
• { - (آکولاد باز)
• } - (آکولاد بسته)
• [ - (کروشه باز)
• ] - (کروشه بسته)

باید بررسی کنید که آیا این رشته معتبر است یا خیر. یک رشته معتبر دارای ویژگی‌های زیر است:

1. هر پرانتز باز، توسط یک پرانتز بسته از همان نوع بسته شود.
2. پرانتزهای باز باید به ترتیب صحیح بسته شوند. به عنوان مثال، نمی‌توانید ابتدا یک پرانتز بسته قرار دهید و سپس آن را با یک پرانتز باز ببندید.
3. برای هر پرانتز بسته، یک پرانتز باز از همان نوع وجود داشته باشد. هیچ پرانتز بسته اضافی نباید وجود داشته باشد.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

قیدها:

• 1 <= s.length <= 104
• s فقط شامل موارد '()[]{}'.

راه حل ۱: پشته (Stack)

رشته براکت s را پیمایش کنید.

هنگام برخورد با براکت باز، براکت باز فعلی را به پشته (stack) اضافه کنید. هنگام برخورد با براکت بسته، عنصر بالایی stack را خارج کنید (اگر stack خالی است، مستقیما مقدار نامعتبر را برگردانید) و بررسی کنید که آیا با براکت باز هم‌نوع مطابقت لازم را داشته باشد. اگر مطابقت ندارد، مستقیما نامعتبر را برگردانید.

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

تفاوت بین این دو روش فقط زمان تبدیل براکت‌ها است. یکی هنگام اضافه کردن به پشته و دیگری هنگام خارج کردن از پشته انجام می شود.

در انتهای پیمایش، اگر پشته خالی باشد، به این معنی است که رشته براکت معتبر است، پس مقدار معتبر را برگردانید. در غیر این صورت مقدار نامعتبر را برگردانید.

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

func isValid(s string) bool {
 stk := []rune{}
 for _, c := range s {
  if c == '(' || c == '{' || c == '[' {
   stk = append(stk, c)
  } else if len(stk) == 0 || !match(stk[len(stk)-1], c) {
   return false
  } else {
   stk = stk[:len(stk)-1]
  }
 }
 return len(stk) == 0
}

func match(l, r rune) bool {
 return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}')
}