SHARE
TWEET

Generate Parenthesis

asrivenki Nov 11th, 2019 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Parenthesis {
  2.   String str;
  3.   int openCount;
  4.   int closeCount;
  5.  
  6.   public Parenthesis(String str, int openCount, int closeCount) {
  7.     this.str= str;
  8.     this.openCount = openCount;
  9.     this.closeCount = closeCount;
  10.   }
  11. }
  12.  
  13. class Solution {
  14.    
  15.     public List<String> generateParenthesis(int num) {
  16.         List<String> result = new ArrayList<String>();
  17.         generateParenthesisHelper(num, "", 0, 0, result);
  18.         return result;
  19.        
  20.     }
  21.    
  22.     public void generateParenthesisHelper(int num, String curr, int openCount, int closeCount, List<String> result) {
  23.         if((openCount == num) && (closeCount == num))
  24.             result.add(curr);
  25.        
  26.         if(openCount < num) {
  27.             generateParenthesisHelper(num, curr + "(", openCount+1, closeCount, result);
  28.         }
  29.        
  30.         if(closeCount < openCount) {
  31.             generateParenthesisHelper(num, curr + ")", openCount, closeCount+1, result);
  32.         }    
  33.                      
  34.     }
  35.    
  36.    
  37.    
  38.     public List<String> generateParenthesisBreadthWise(int num) {
  39.         List<String> result = new ArrayList<String>();
  40.         Parenthesis initial = new Parenthesis("", 0, 0);
  41.         Queue<Parenthesis> q = new LinkedList<>();
  42.  
  43.         q.add(initial);
  44.  
  45.         while(!q.isEmpty()) {
  46.           Parenthesis p = q.poll();
  47.           if(p.openCount == num && p.closeCount == num) {
  48.             result.add(p.str);  
  49.           } else {
  50.             if(p.openCount < num) {
  51.               Parenthesis p1 = new Parenthesis(p.str + "(", p.openCount + 1, p.closeCount);
  52.               q.add(p1);
  53.             }
  54.             if(p.openCount > p.closeCount) {
  55.               Parenthesis p2 = new Parenthesis(p.str + ")", p.openCount, p.closeCount + 1);
  56.               q.add(p2);
  57.             }
  58.           }
  59.         }
  60.  
  61.         return result;
  62.     }
  63. }
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