Simple Iteration java solution(use StringBuilder)


  • 0
    Z

    use this thinking(this algorithm can be used to solve permutation problem as well):

    when n=1: "()"
    when n=2: we can insert a set of "()" to the above position at index of 0, 1, 2, so we have "()()","(())","()()", since there is duplicate result, we add a condition that if exist already, not add to the result.
    when n=3: repeat above steps to "()()", "(())".
    .when n=4 ................
    .
    .
    .

    public class Solution {
    
        public List<String> generateParenthesis(int n) {
        
        StringBuilder str=new StringBuilder();
        
        List<String> res=new ArrayList<String>();
         str.append("()");
        res.add(str.toString());
        
        if(n==1) return res;
        while(n>1)
        {
          int lenres=res.size();
          
          for(int j=0; j<lenres; j++)
          {
          StringBuilder str1=new StringBuilder(res.remove(0));
          
          int lens=str1.length();
          for(int i=0; i<lens; i++)
          {
              StringBuilder str2=new StringBuilder(str1);
              str2.insert(i,"()");
              if(!res.contains(str2.toString())) res.add(str2.toString());
          }
          }
          n--;
        }
        return res;
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.