给一个只由’(‘和’)'组成的字符串找出其中最长的连续合法子串长度。(来源Leetcode)
很明显可以用动态规划,我也是这么想的
构建dp[len][len], dp[i][j]表示以i开头j结尾的子串中最长子串。s表示字符串然后给出递推式
结果分析,虽说用了动态规划的思想但是明显时间和空间复杂度过高,尽管有一定技巧性但本质上昰
以下内容主要是来源于LeetCode上的解决方案,我主要是翻译了一下主要分为暴力,动态规劃堆栈,无需额外空间法
找出所有偶数子串,然后使用堆栈判断是否是合法括号思而行
只需一个一维动态数组,dp[i]表示以第i个字符結尾的合法子串长度。换句话说合法子串包括第i个字符。时间复杂度和空间复杂度分别为
鼡两个变量left和right存储左右括号思而行数量当left == right,表示当前最大子串长度当right > left,表示遇到不合法两个变量置0。当遇到"(()"此时该方法失效,因此从左往右扫然后从右往左扫,即可完美解决所有情况