问题描述:
给定一个只包含 ‘(’ 和 ‘)’ 的字符串,找出其中有效括号的长度。
样例输入: “((()))()(” 样例输入: 8
思路分析:利用双指针,不断地寻找右括号即可。
代码如下:
import java.util.Scanner; public class LongestValidParentheses { public static int longestValidParentheses(String s) { int st=0; int et=0; int len=0; for (int i = 0; i <s.length() ; i++) {//寻找第一个右括号 if (i!=0&&s.charAt(i)==')')//除去第一位 { et=i; break; } } if (et==0) return len; st=et-1; while (et<s.length()&&st>=0) { if (s.charAt(et)==')'&&s.charAt(st)=='(') { len+=2; st-=1; et+=1; if (st<0) { int temp=et; for (int i = et+1; i <s.length() ; i++) {//寻找右括号 if (s.charAt(i)==')') { et=i; break; } } if (temp==et) return len; else st=et-1; } } else { int temp=et; for (int i = et+1; i <s.length() ; i++) {//寻找右括号 if (s.charAt(i)==')') { et=i; break; } } if (temp==et) return len; else st=et-1; } } return len; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); String s=scanner.nextLine(); int res=longestValidParentheses(s); System.out.println(res); } }运行结果见下: