SHARE
TWEET

BracketSequenceDiv1

a guest Mar 29th, 2016 236 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class BracketSequenceDiv1 {
  4.   static final int N = 40;
  5.  
  6.   boolean order(int l, int m, int r) {
  7.     return l <= m && m <= r;
  8.   }
  9.  
  10.   public String checkData(String s) {
  11.     int n = s.length();
  12.     if (!order(1, n, N))
  13.       return "s must contain between 1 and 40 characters, inclusive.";
  14.  
  15.     for (int i = 0; i < n; ++i) {
  16.       char c = s.charAt(i);
  17.       if (c != '(' && c != ')' && c != '[' && c != ']')
  18.         return "Each character in s must be one of '(', ')', '[', ']'.";
  19.     }
  20.  
  21.     return "";
  22.   }
  23.  
  24.   boolean pairs(char l, char r) {
  25.     return (l == '(' && r == ')') ||
  26.            (l == '[' && r == ']');
  27.   }
  28.  
  29.   public long count(String s) {
  30.     int n = s.length();
  31.     long[][] d = new long[n + 1][n + 1];
  32.  
  33.     for (int k = 0; k <= n; ++k)
  34.       d[k][k] = 1;
  35.  
  36.     for (int len = 1; len <= n; ++len)
  37.       for (int i = 0; i + len <= n; ++i) {
  38.         int j = i + len;
  39.  
  40.         d[i][j] = d[i + 1][j];
  41.  
  42.         for (int k = i + 1; k < j; ++k)
  43.           if (pairs(s.charAt(i), s.charAt(k)))
  44.             d[i][j] += d[i + 1][k] * d[k + 1][j];
  45.       }
  46.  
  47.     return d[0][n] - 1;
  48.   }
  49.  
  50.   public static void main(String[] args) {
  51.     BracketSequenceDiv1 solver = new BracketSequenceDiv1();
  52.     String s = "()()";
  53.     System.out.println(solver.count(s));
  54.   }
  55. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top