Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class BracketSequenceDiv1 {
- static final int N = 40;
- boolean order(int l, int m, int r) {
- return l <= m && m <= r;
- }
- public String checkData(String s) {
- int n = s.length();
- if (!order(1, n, N))
- return "s must contain between 1 and 40 characters, inclusive.";
- for (int i = 0; i < n; ++i) {
- char c = s.charAt(i);
- if (c != '(' && c != ')' && c != '[' && c != ']')
- return "Each character in s must be one of '(', ')', '[', ']'.";
- }
- return "";
- }
- boolean pairs(char l, char r) {
- return (l == '(' && r == ')') ||
- (l == '[' && r == ']');
- }
- public long count(String s) {
- int n = s.length();
- long[][] d = new long[n + 1][n + 1];
- for (int k = 0; k <= n; ++k)
- d[k][k] = 1;
- for (int len = 1; len <= n; ++len)
- for (int i = 0; i + len <= n; ++i) {
- int j = i + len;
- d[i][j] = d[i + 1][j];
- for (int k = i + 1; k < j; ++k)
- if (pairs(s.charAt(i), s.charAt(k)))
- d[i][j] += d[i + 1][k] * d[k + 1][j];
- }
- return d[0][n] - 1;
- }
- public static void main(String[] args) {
- BracketSequenceDiv1 solver = new BracketSequenceDiv1();
- String s = "()()";
- System.out.println(solver.count(s));
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement