16 June 2018

Generate Parentheses



Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example,
 i/p: 
n = 3

o/p:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
] 
 
import java.util.*;
public class NewClass2 {
  
    Set<String> br=new HashSet<String>();
    void generate()
    {
      
        for(String i:br)
        System.out.println(i);
      
    }
    void checkBalanced(String name)
    {
        HashMap<Character,Character> hm=new HashMap<Character,Character>();


        hm.put('(',')');


        Stack<Character> st=new Stack<Character>();


        int c=0;


            for(int i=0;i<name.length();i++)
            {
                if(hm.containsKey(name.charAt(i)))
                {
                    st.push(name.charAt(i));
                }else if(hm.containsValue(name.charAt(i)))
                {
                    if(!st.empty() && hm.get(st.peek())==name.charAt(i))
                    {
                        st.pop();
                    }else
                    {c=1;
                      break;
                    }
                }else
                {
                      c=1;
                      break;
                }
            }
            if(c==0 && st.empty())
                br.add(name);
      
    }

    String swap(String s,int i,int j)
    {
        char c[]=s.toCharArray();
        char t=c[i];
        c[i]=c[j];
        c[j]=t;
        return String.valueOf(c);
    }
  
    void per(String s,int l,int r)
    {
                if(l==r)
                checkBalanced(s);
        for(int i=l;i<r;i++)
        {
            s=swap(s,l,i);
            per(s,l+1,r);
            s=swap(s,l,i);
        }
    }
    public static void main(String args[])
    {
        int n=3;
        String s="";
        for(int i=0;i<n;i++)
        {
            s+="()";
        }
        NewClass2 ob=new NewClass2();
        ob.per(s,0,s.length());
        ob.generate();
    }
}

No comments:

Post a Comment