Leetcode parentheses matching problem -- 32. The longest parentheses effectively

32. Longest Valid Parentheses

Title description:

1. Stack

Idea: When we first see the parentheses, our first thought must be to use the stack to perform a parenthesis match, and our problem is no exception;

We first find all index numbers that can be matched, and then find the longest continuous sequence!

For example: s = )(()()), we can use the stack to find,

Position 2 and position 3 match,

Position 4 matches position 5,

Position 1 and position 6 match,

This array is: 2,3,4,5,1,6 This is found through the stack, we sort by increasing!1,2,3,4,5,6

Find the length of the longest continuous sequence of the array is the longest effective bracket length!

Entry code:

public int longestValidParentheses(String s) {if (s.length() < 2) return 0;Stack stack = new Stack<>();stack.push(-1);int res = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(')stack.push(i);else {stack.pop();if (stack.isEmpty())stack.push(i);elseres = Math.max(res,i - stack.peek());}}return res;}

Time complexity: O(n)

Space complexity: O(1)

2. Dynamic programming (space for time)

Thinking:When we use dynamic programming, we mainly consider several situations:

When s.charAt(i) == '(', dp[i] = 0;

When s.charAt(i) == ')', we divide again:

When s.charAt(i - 1) == '(', dp[i] = dp[i - 2] + 2;

Conversely, when s.charAt(i - 1) == ')', it is divided into:

dp[i] = dp[i] = dp[i - 1] + 2 + dp[i - dp when s.charAt(i - dp[i - 1] - 1) == '('[i - 1] - 2]

dp[i] = 0;

Entry code:

 public static int longestValidParentheses(String s) {if (s.length() < 2) return 0;int[] dp = new int[s.length()];//The first symbol has a length of 0 no matter whatdp[0] = 0;int max = 0;for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == '(')dp[i] = 0;elseif (s.charAt(i - 1) == '(') {dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;} else {if (i - dp[i - 1] -1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(')dp[i] = i - dp[i - 1] - 2>=0? dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]: dp[i - 1] + 2;else dp[i] = 0;}max = Math.max(dp[i], max);}return max;}

Time complexity: O(n)

Space complexity: O(n)

Summary: This is a typical bracket matching question, from stack to dynamic programming, using space for time, you can watch it repeatedly, you must understand it thoroughly!