DP (一): 最长括号子串

ゝ一纸荒年。 2022-02-16 07:44 181阅读 0赞

### 最长括号子串 ###

*  前言
 *  思路
 *  代码 (C语言)

# 前言 #

这个系列用来学动态规划.  
[题目链接在此][Link 1]

题目要求就是给你一个只有小括号的字符串, 让你算一下最长的合法子串长度.

不过这题和最长回文子串还是有些区别, 我一开始用的回文子串的思路来写DP发现非常麻烦还没写对, 最后改用的栈, 发现我的方法比100%的其他使用者都快而且使用内存都小.

# 思路 #

维护两个数据结构: 栈 (stack) 和容器 (count)  
栈用来装左括号的位置 (下标), count\[i\] 表示字符串第 i 个位置是合法的  
逻辑就是, 从头开始逐字符读字符串, 如果是左括号, 就把它的下标压栈, 如果是右括号, 如果栈非空, 就 pop 一下, 然后会获得两个位置, 一个是当前 for 循环的位置 i (即右括号的位置) , 一个是 pop 的值 j (即那个左括号的位置), 然后 count\[i\] = count\[j\] = 1, 表示这两个位置是合法的.  
最后给 count 数组来一次最长连续子数组和即可.

# 代码 (C语言) #

#include <string.h>
    #include <stdlib.h>
    
    int longestValidParentheses(char* s) { 
        if (!s) return 0;
        int len = strlen(s);
        if (!len) return 0;
        int* count = (int*)malloc(sizeof(int) * len);
        int* stack = (int*)malloc(sizeof(int) * len);
        memset(count, 0, sizeof(int) * len);
        int sp = 0;
        int maxLen = 0;
        int currentLen = 0;
        for (int i = 0; i < len; i++) { 
            if (s[i] == '(') { 
                stack[sp++] = i;
            } else if (sp) { 
                count[i] = 1;
                count[stack[--sp]] = 1;
            } 
        }
        for (int i = 0; i < len; i++) { 
            if (!count[i]) { 
                if (currentLen > maxLen) maxLen = currentLen;
                currentLen = 0;
            } else { 
                currentLen++;
            }
        }
        if (currentLen > maxLen) maxLen = currentLen;
        free(stack);
        free(count);
        return maxLen;
    }

[Link 1]: https://leetcode.com/problems/longest-valid-parentheses/