سوال روزانه 678 لیت کد - Valid Parenthesis String

به سه روش حلش میکنم، یه روش استک، دو روش برنامه نویسی پویا یا همون داینامیک پروگرمینگ.

پیچیدگی زمانی راه حل استک: O(n) یه حلقه ی فور داریم
پیچیدگی حافظه راه حل اسک: O(n) دو تا استک استفاده میکنیم

پیچیدگی زمانی راه حل دوم: O(n^3)
تعداد n^2 تا زیر مسئله داریم و برای حساب کردن هر زیر مسئله یه حلقه ی فور داریم که در مجموع میشه n^3
پیچیدگی حافظه راه حل دوم: O(n^2) به خاطر جدول dp

پیچیدگی زمانی راه حل سوم: O(n^2) اینجا برای حساب کردن هر زیر مسئله حلقه ی فور نداریم.
پیچیدگی حافظه راه حل سوم: O(n^2) مثل راه حل دوم



لینک سوال:
https://leetcode.com/problems/valid-p...