الگوریتم در گولنگ (قسمت سوم): Valid Parentheses و فرار از تله‌های Tech Lead!

در قسمت قبلی با هم الگوریتم Two Sum را شخم زدیم و دیدیم چطور یک HashMap ساده می‌تواند ما را از شر حلقه‌های تودرتو و نگاه‌های سنگین Tech Lead نجات دهد. قصد داریم در این مجموعه مقاله، مسیر حل الگوریتم‌ها را با همین فرمون جلو برویم.

الگوریتم دومی که مورد بحث قرار می‌دهیم، یکی دیگر از غول‌های مرحله اول (Screening) مصاحبه‌های بین‌المللی است: Valid Parentheses (پرانتزهای معتبر).

صورت سوال

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Input: s = “()”

Output: true

Input: s = “()[]{}”

Output: true

Input: s = “(]”

Output: false

Input: s = “([)]”

Output: false

Constraints:

• 1≤ s.length ≤10 ^4

• s consists of parentheses only '()[]{}'.

درک مسئله: ذهن انسان در برابر ماشین

بیایید بی‌درنگ برویم سراغ مسئله. اگر به عنوان یک انسان به رشته "{[()]}" نگاه کنیم، مغز ما به طور خودکار تقارن را تشخیص می‌دهد. چشم ما از وسط شروع می‌کند، می‌بیند () کنار هم هستند، بعد [] آن‌ها را احاطه کرده و در نهایت {}. در کسری از ثانیه می‌گوییم “معتبر است!”.

اما کامپیوتر کورِ بیچاره تقارن سرش نمی‌شود. او رشته را مثل یک تونل تاریک می‌بیند و فقط می‌تواند کاراکترها را یکی‌یکی از چپ به راست بخواند (پیمایش کند).

پس ذهن برخی از برنامه‌نویسان تازه‌کار می‌رود سراغ یک ایده ظاهراً هوشمندانه: «خب، اگر رشته معتبر باشه، حتماً یک جایی توش () یا [] یا {} چسبیده به هم وجود داره. بیایم تو یه حلقه، هی این جفت‌ها رو پیدا کنیم و حذفشون کنیم. اگر در نهایت هیچی نموند، یعنی رشته معتبره!»

اگر بخواهیم این منطق را تبدیل به کد گولنگ کنیم، به چیزی شبیه به این می‌رسیم:

package main

import (
	"fmt"
	"strings"
)

// Bad Practice: String manipulation in a loop
func isValidBad(s string) bool {
	// Keep looping as long as we find a valid pair
	for strings.Contains(s, "()") || strings.Contains(s, "[]") || strings.Contains(s, "{}") {
		s = strings.ReplaceAll(s, "()", "")
		s = strings.ReplaceAll(s, "[]", "")
		s = strings.ReplaceAll(s, "{}", "")
	}
	// If the string is completely empty, it was valid
	return len(s) == 0
}

func main() {
	fmt.Println(isValidBad("{[()]}")) // true
}

کد کار کرد! اما… (ورود مجدد Tech Lead 😠)

شما با غرور کد را ران می‌کنید، خروجی درست است و فکر می‌کنید الگوریتم را هک کرده‌اید! اما وقتی Tech Lead کد را می‌بیند، دستش را روی پیشانی‌اش می‌گذارد و درخواست یک جلسه 1-on-1 می‌دهد.

چرا این کد در یک مصاحبه واقعی درجا رد می‌شود؟

۱. فاجعه پرفورمنس و تخصیص حافظه (Memory Allocation):

در گولنگ (و خیلی از زبان‌های دیگر)، استرینگ‌ها Immutable (تغییرناپذیر) هستند. یعنی وقتی شما strings.ReplaceAll را صدا می‌زنید، گولنگ رشته قبلی را تغییر نمی‌دهد، بلکه یک رشته کاملاً جدید در حافظه می‌سازد! اگر طول رشته ما 10410^4104 باشد (طبق محدودیت‌ها)، شما دارید هزاران رشته جدید می‌سازید و Garbage Collector را به مرز جنون می‌رسانید.

۲. زمان اجرای وحشتناک (Time Complexity):

هر بار که strings.Contains یا ReplaceAll اجرا می‌شود، کل رشته از اول اسکن می‌شود. پیچیدگی زمانی این روش در بدترین حالت نزدیک به O(n2)O(n^2)O(n2) است.

تغییر زاویه دید: ترفند طلایی

تک‌لید به شما می‌گوید: «به جای اینکه هی رشته رو بسازی و خراب کنی، از ساختار داده‌ای استفاده کن که دقیقاً برای همین کار ساخته شده: Stack (پشته).»

پشته یا LIFO (Last In, First Out) مثل یک دسته بشقاب است. آخرین بشقابی که روی هم می‌گذارید، اولین بشقابی است که برمی‌دارید. در مسئله ما: آخرین براکتی که باز شده، باید اولین براکتی باشد که بسته می‌شود.

فرض کنید رشته ما "{ [ } ]" است:

1. کاراکتر { را می‌بینیم. چون باز است، می‌گذاریمش توی پشته.

2. کاراکتر [ را می‌بینیم. باز است، می‌رود روی پشته (الان بالاترین عنصر پشته [ است).

3. کاراکتر } را می‌بینیم. این یک براکت بسته است! باید بررسی کنیم آیا با بالاترین عنصر پشته جفت می‌شود؟ بالاترین عنصر [ است. آیا } با [ جفت است؟ خیر! پس رشته نامعتبر است.

با این روش، فقط یک بار روی رشته حرکت می‌کنیم (Single Pass).

راه‌حل بهینه و حرفه‌ای (The Optimal Solution)

در گولنگ ساختار داده اختصاصی به نام Stack نداریم، اما نیازی هم نداریم! اسلایس‌ها (Slices) در گولنگ به راحتی نقش یک پشته را بازی می‌کنند.

کدمان را به شکلی می‌نویسیم که پیچیدگی زمانی آن O(n) و پیچیدگی فضایی آن حداکثر O(n) باشد.

func isValid(s string) bool {
	// Base check: If the length is odd, it's impossible to be valid
	if len(s)%2 != 0 {
		return false
	}

	// Map to keep track of matching brackets
	// Key: Closing bracket, Value: Corresponding Opening bracket
	brackets := map[rune]rune{
		')': '(',
		'}': '{',
		']': '[',
	}

	// Our stack (using a slice of runes)
	var stack []rune

	for _, char := range s {
		// Is it a closing bracket? (Checking if it exists as a key in our map)
		if openBracket, isClose := brackets[char]; isClose {
			
			// 1. Stack must not be empty
			// 2. The top of the stack must match the required opening bracket
			if len(stack) > 0 && stack[len(stack)-1] == openBracket {
				// Pop: Remove the top element from the stack
				stack = stack[:len(stack)-1]
			} else {
				// Mismatch or empty stack with a closing bracket
				return false
			}
		} else {
			// It's an opening bracket, push it onto the stack
			stack = append(stack, char)
		}
	}

	// If the stack is empty at the end, all brackets were matched perfectly!
	return len(stack) == 0
}

کالبدشکافی خط به خط:

• if len(s)%2 != 0:

این یک نکته طلایی (Early Return) است. اگر طول رشته فرد باشد (مثلاً ۳)، محال است تمام براکت‌ها جفت شوند. با همین یک خط (O(1)O(1)O(1))، کلی از ورودی‌های غلط را بدون محاسبات سنگین فیلتر می‌کنیم. مصاحبه‌گرها عاشق این بهینه‌سازی‌های کوچک هستند!

• brackets := map[rune]rune{ ... }:

استفاده از مپ باعث می‌شود اگر فردا روزی مدیر محصول گفت «براکت‌های < > را هم ساپورت کنید»، کدهای ما پر از if/else های زشت نشود.

• var stack []rune:

ما پشته خود را به صورت یک اسلایس از نوع rune (نماینده کاراکترهای یونیکد در گو) تعریف می‌کنیم.

• if openBracket, isClose := brackets[char]; isClose:

یک تیر و دو نشان! هم چک می‌کنیم کاراکتر فعلی جزو براکت‌های بسته (کلیدهای مپ) هست یا نه، و هم براکتِ بازِ متناظرش را می‌گیریم.

• stack[len(stack)-1]:

این دستور دقیقاً بالاترین (آخرین) عنصر پشته را می‌خواند.

• stack = stack[:len(stack)-1]:

این عملیات Pop در گولنگ است! با استفاده از قابلیت Slicing، به گولنگ می‌گوییم: «یک اسلایس جدید بساز که شامل همه عناصر قبلی باشد، به جز آخری.»

• return len(stack) == 0:

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

تست کیس‌ها (Edge Cases) و اثبات کد

دوباره سراغ Table-Driven Tests می‌رویم تا به Tech Lead ثابت کنیم کدمان ضدگلوله است.

package main

import "testing"

func TestIsValid(t *testing.T) {
	tests := []struct {
		name     string
		input    string
		expected bool
	}{
		{"Empty string", "", true},
		{"Simple valid", "()", true},
		{"Multiple valid", "()[]{}", true},
		{"Nested valid", "{[()]}", true},
		{"Simple invalid", "(]", false},
		{"Wrong order", "([)]", false},
		{"Odd length", "()[", false}, // Killer Case 1
		{"Start with close", "][", false}, // Killer Case 2
		{"Only open brackets", "((((", false}, // Killer Case 3
		{"Only close brackets", "))))", false}, // Killer Case 4
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			result := isValid(tt.input)
			if result != tt.expected {
				t.Errorf("isValid(%q) = %v; want %v", tt.input, result, tt.expected)
			}
		})
	}
}

جمع‌بندی نکات این الگوریتم:

1. قدرت پشته (Stack): هرجا در الگوریتم‌ها با مفاهیمی مثل “ترتیب معکوس”، “تقارن تو در تو” یا “Undo” مواجه شدید، اول از همه به Stack فکر کنید.

2. فرار از String Manipulation: دستکاری رشته‌ها در حلقه‌های طولانی یک قاتل خاموش پرفورمنس است.

3. مدیریت Edge Case ها: حالت‌هایی مثل شروع شدن با براکت بسته ]، یا پر ماندن پشته در انتها ((( دقیقاً همان جاهایی هستند که تفاوت یک جونیور و سنیور را در مصاحبه مشخص می‌کنند.