Optimizing the back-tracking solution in C#


  • 0
    D

    public class Solution {
    private void Backtrack(List<String> list, LinkedList<char> charList, int open, int close, int max){

        if(charList.Count == max*2){
            char[] buffer = new char[charList.Count];
            
            int i=0;
            foreach(char item in charList){
                buffer[i++] = item;
            }
            
            list.Add(new string(buffer));
                        
            return;
        }
        
        if(open < max){
            charList.AddFirst(')');
            Backtrack(list, charList, open+1, close, max);
            charList.RemoveFirst();
        }
        if(close < open){
            charList.AddFirst('(');
            Backtrack(list, charList , open, close+1, max);
            charList.RemoveFirst();
        }
    }
    
    public IList<string> GenerateParenthesis(int n) {
        List<String> list = new List<String>();
        LinkedList<char> charList = new LinkedList<char>();
        Backtrack(list, charList, 0, 0, n);
        return list;    
    }
    

    }


    I planned around with Yan's solution, which was nice, but made some optimizations, and, also, ported it to C#. I removed the string concats, and, also, used a LinkedList<char> instead of string. It is smoking fast! Give it a try.


Log in to reply
 

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