داشتم تجربه مصاحبه یکی از دوستان را میخواندم که یک سوالی پرسیده بودند که خیلی زمان از بررسی موضوع مشابهی برام گذشته بود بنابراین تصمیم گرفتم یک فلش بک به این موضوع داشته باشم و با شما به اشتراک بذارم.
خب فرض کنید یک عبارت بهمون میدن مثل "abba" و یا "madam" و حالا میگن پالیندروم بودنش رو بررسی کنید.(یعنی reverse عبارت با خود عبارت یکی بشه).
خب این کار رو با ساختار stack میشه به راحتی انجام داد.کدشو نوشتم و در پایین قرار دادم.
خب برای راحتی کار یک extension متد نوشتم که روی string ها کار میکنه .
در ابتدا نیمه اول اون عبارت رو وارد یک stack میکنیم. (البته اگر تعداد کارکتر ها فرد باشه ، عنصر وسط وارد نمیشه) .حالا تا اینجا ما یک پشته داریم که مثلا برای عبارت madam داخلش am قرار گرفته (a در بالای پشته و m در پایین پشته). در مواقعی که تعداد کارکتر ها فرد هست ، عنصر وسط سر جاش باقی میمونه و اصلا نیازی به چک کردنش نیست برای همین چک میکنیم که اگر تعدا کارکتر ها فرد بود ، i رو اضافه میکنیم .
در مرحله بعد از نصفه دوم پشته تا انتها جلو میریم و هر بار از پشته یک حرف رو pop میکنیم و قیاس با مقدار ادامه نصفه دوم پشته میکنیم. اگر مساوی نبودند قاعدتا اون رشته Palindrome نیست و این کار را تا زمان تمام شدن رشته انجام میدهیم.
با فرض بر اینکه push و pop کردن هزینه اجرایی 1 دارن برامون ، چون حلقه های while ما تا len/2 جلو میرن پس میتونیم نتیجه بگیریم پیچیدگی زمانی ما همین میشه.
