Generate Parentheses

Problem description:

Given a non negative number n, generate all possible combinations of strings that can be formed by n-pairs of well-formed parentheses, for example:

for n = 2
a solution is: “(())”, “()()”

and for n = 3
a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Solution:

We could use a simple Depth First Search (DFS) approach to recursively build the set of solutions, see the solution code below and then read the explanation:

    void generateParentheses(int n) {
        dfs("", n, n);
    }
    void dfs(String s, int left, int right) // build the set of solutions using DFS approach
    {
        if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
            System.out.println(s);
        if(left > 0) // while we have left parentheses to add, just add them
            dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
        if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
            dfs(s + ")", left, right - 1);
    }

Let’s work on the simplest example to explain how it works:

for n = 2 we know that we have 2 left parentheses and 2 right parentheses so for each recursive call we are going to take 2 decisions:
1.- Can we put a left parentheses?
2.- Can we put a right parentheses?

How do we know if we are able to put a left or right parentheses at each recursive call?
We can put a left parentheses as long as we have at least one left parentheses available but for the right ones we can add them only when we have more right parentheses available because we know that we have already added the corresponding left parentheses before adding the right one.

Do you have any question/comment/suggestion? Please leave your comment below.

Advertisements

Clone a graph

Problem Description

Given an undirected graph write a function that returns a CLONE of that graph, example of an undirected graph:

1  ———-  2

|            /

|      /

3

Each node has a label and a list of neighbors (represented as an ArrayList).

Solution code


map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); //This map is gonna be used to check if a node has been already created,

//we use the original node as a key and the clone node as the value.

UndirectedGraphNode clone(UndirectedGraphNode node)
{
    if(map.containsKey(node)) //if the current node has been already cloned then just return the cloned node
        return map.get(node);

    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);  // create the clone node
    map.put(node, newNode); // put the clone into the map

    ArrayList<UndirectedGraphNode> nei = new ArrayList<UndirectedGraphNode>(); //create a new arraylist of neighbors for the new node

// loop through the neighbors of the original node and call our function recursively to build the new list of neighbors
    for(UndirectedGraphNode n : node.neighbors)
        nei.add(clone(n));

    newNode.neighbors = nei;
    return newNode;
}

Explanation:

It is basically a DFS traversal (http://en.wikipedia.org/wiki/Depth-first_search),  the clone function is called for every node and it returns the new cloned node with it’s corresponding list of neighbors, the key part here is that we need to keep track of those nodes that we have already cloned to avoid infinite loops, this is done with the HasMap.