FilesExpand file tree

 master

/

032_LongestValidParentheses32.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

107 lines (98 loc) · 2.83 KB

 master

/

032_LongestValidParentheses32.java

Copy path

Top

File metadata and controls

• Code
• Blame

107 lines (98 loc) · 2.83 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

/**

* Given a string containing just the characters '(' and ')', find the length

* of the longest valid (well-formed) parentheses substring.

*

* Example 1:

* Input: "(()"

* Output: 2

* Explanation: The longest valid parentheses substring is "()"

*

* Example 2:

* Input: ")()())"

* Output: 4

* Explanation: The longest valid parentheses substring is "()()"

*/

public class LongestValidParentheses32 {

public int longestValidParentheses(String s) {

int len = s.length();

if (len <= 1) return 0;

boolean[] valid = new boolean[len];

Stack<Integer> stack = new Stack<>();

char[] chars = s.toCharArray();

for (int i=0; i<len; i++) {

if (chars[i] == '(') {

stack.push(i);

} else {

if (!stack.isEmpty()) {

int left = stack.pop();

valid[left] = true;

valid[i] = true;

}

}

}

int curr = 0;

int max = 0;

for (int i=0; i<len; i++) {

if (valid[i]) {

curr++;

} else {

max = Math.max(max, curr);

curr = 0;

}

}

return Math.max(max, curr);

}

/**

* https://leetcode.com/problems/longest-valid-parentheses/solution/

*/

public int longestValidParentheses2(String s) {

int maxans = 0;

Stack<Integer> stack = new Stack<>();

stack.push(-1);

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') {

stack.push(i);

} else {

stack.pop();

if (stack.empty()) {

stack.push(i);

} else {

maxans = Math.max(maxans, i - stack.peek());

}

}

}

return maxans;

}

/**

* https://leetcode.com/problems/longest-valid-parentheses/solution/

*/

public int longestValidParentheses3(String s) {

int left = 0, right = 0, maxlength = 0;

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') {

left++;

} else {

right++;

}

if (left == right) {

maxlength = Math.max(maxlength, 2 * right);

} else if (right >= left) {

left = right = 0;

}

}

left = right = 0;

for (int i = s.length() - 1; i >= 0; i--) {

if (s.charAt(i) == '(') {

left++;

} else {

right++;

}

if (left == right) {

maxlength = Math.max(maxlength, 2 * left);

} else if (left >= right) {

left = right = 0;

}

}

return maxlength;

}

}