GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Java/DynamicProgramming/LongestValidParentheses.java at master · kay2012/Java Expand file tree/ Copy pathLongestValidParentheses.javaMore file actions 61 lines (49 loc) · 1.55 KB / Copy pathLongestValidParentheses.javaFile metadata and controls61 lines (49 loc) · 1.55 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package DynamicProgramming; import java.util.Scanner; /** * Given a string containing just the characters '(' and ')', find the length of * the longest valid (well-formed) parentheses substring. * * @author Libin Yang (https://github.com/yanglbme) * @since 2018/10/5 */ public class LongestValidParentheses { public static int getLongestValidParentheses(String s) { if (s == null || s.length() < 2) { return 0; } char[] chars = s.toCharArray(); int n = chars.length; int[] res = new int[n]; res[0] = 0; res[1] = chars[1] == ')' && chars[0] == '(' ? 2 : 0; int max = res[1]; for (int i = 2; i < n; ++i) { if (chars[i] == ')') { if (chars[i - 1] == '(') { res[i] = res[i - 2] + 2; } else { int index = i - res[i - 1] - 1; if (index >= 0 && chars[index] == '(') { // ()(()) res[i] = res[i - 1] + 2 + (index - 1 >= 0 ? res[index - 1] : 0); } } } max = Math.max(max, res[i]); } return max; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { String str = sc.nextLine(); if ("quit".equals(str)) { break; } int len = getLongestValidParentheses(str); System.out.println(len); } sc.close(); } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |