Leetcode/src/LongestValidParentheses/program.cpp at master · robling/Leetcode · GitHub

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
#include "../include/prevector.h"

/// \return false when no barckets can be matched
inline bool MatchBrackets(int* triMask, int length)
{
	int num = 0;
	for (int i = 0; i != length; i++)
	{
		if (triMask[i] == 1)
		{
			for (int j = i + 1; j != length; j++)
			{
				if (triMask[j] == 0)
					continue;
				if (triMask[j] == 1)
					break;
				if (triMask[j] == 2)
				{
					++num;
					triMask[i] = 0;
					triMask[j] = 0;
					break;
				}
			}
		}
	}
	if (num != 0)
		return true;
	else
		return false;
}
int longestValidParentheses(string s) {
	int *triMask = new int[s.length()];
	for (int i = 0; i != s.length(); i++)
	{
		int tmp = 100;
		switch (s[i])
		{
		case '(':
			tmp = 1;
			break;
		case ')':
			tmp = 2;
			break;
		default:
			assert(false);
			break;
		}
		triMask[i] = tmp;
	}
	while (MatchBrackets(triMask, s.length())){}
	int maxLength = 0;
	for (int i = 0; i != s.length(); i++)
	{
		int tmp = 0;
		if (triMask[i] == 0)
		{
			++tmp;
			for (int j = i + 1; j != s.length(); j++)
			{
				if (triMask[j] == 0)
					++tmp;
				else
					break;
			}
			if (tmp > maxLength)
				maxLength = tmp;
		}
	}
	delete[] triMask;
	return maxLength;
}

int Mymain()
{
    vector<string> testData = {"()()())))(((", "()))((())((()(("};
    for (auto s : testData)
    {
        cout << s << ": ";
        cout << longestValidParentheses(s) << "\n";
    }
		return 0;
}