1.问题

1、已知一个字符串都是由左括号(和右括号)组成，判断该字符串是否是有效的括号组合。 例子： 有效的括号组合:()(),(()),(()()) 无效的括号组合:(,()),((),()(() 2、题目进阶： 已知一个字符串都是由左括号(和右括号)组成，返回最长有效括号子串的长度。

2.code

//1.当遇到不是( )的符号时 直接返回false; //2.遇到 ) status<0 返回false //3.遇到( status就++ package com.ncst.offer.ch1; /** * @author i * @create 2020/7/1 11:55 * @Description */ public class Problem_01_ParenthesesProblem { //1.当遇到不是( )的符号时 直接返回false; //2.遇到 ) status<0 返回false //3.遇到( status就++ public static boolean isValid(String str){ if (str == null || str.length() == 0){ return false; } int status = 0; char[] chs = str.toCharArray(); for (int i = 0; i < chs.length; i++) { if (chs[i]!='('&&chs[i]!=')'){ return false; } if (chs[i] == ')' && --status<0){ return false; } if (chs[i] == '('){ status++; } } return status == 0; } public static int maxLength(String str) { if (str == null || str.equals("")) { return 0; } char[] chas = str.toCharArray(); int[] dp = new int[chas.length]; int pre = 0; int res = 0; for (int i = 1; i < chas.length; i++) { if (chas[i] == ')') { pre = i - dp[i - 1] - 1; if (pre >= 0 && chas[pre] == '(') { dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0); } } res = Math.max(res, dp[i]); } return res; } public static void main(String[] args) { String str = "()()()"; System.out.println(isValid(str)); String str2 = "()()())"; System.out.println(isValid(str2)); } }