241. Different Ways to Add Parentheses -- Leet Code- Java -Solution

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output:

Solution:

import java.util.ArrayList;

import java.util.List;

public class Solution {

    public List<Integer> diffWaysToCompute(String input) {

   

    List<Integer> res = new ArrayList<Integer>();

        

        for(int i = 0 ; i < input.length() ; i++){

        char c = input.charAt(i);

            if(input.charAt(i) == '-' || input.charAt(i) == '+' || input.charAt(i) == '*' ){

                List<Integer> lis1 = diffWaysToCompute(input.substring(0,i));

                List<Integer> lis2 = diffWaysToCompute(input.substring(i + 1));

                

                for(int item1:lis1 ){

                for(int item2:lis2){

                if(c == '-'){

                res.add(item1 - item2);

                }

                else if(c == '+'){

                res.add(item1 + item2);

                }

                else{

                res.add(item1 * item2);

                }

                }

                }

            }

        }

        if(res.size() == 0) {

        res.add(Integer.valueOf(input));

        }

        

        return res;

        

    }

}

Java -Solution- To find Articulation points in a graph

Find Articulation points in a graph so that we can divided the graph into two connected graphs.

Solution:

import java.util.Iterator;
import java.util.LinkedList;

public class Graph {

private int vertices; ;
private LinkedList<Integer> graph[];

private int time;

static final int NIL = -1;
int visited[];

//keep the distance from origin
private int distance[];

//keep the record of lowest distance of subtree
private int lowestAdj[];

//track the parent of vertices
private int parent[];

//articulate points store
private int articulatePoints[];


public Graph(int vertices){
this.vertices = vertices;
graph = new LinkedList[vertices];
visited = new int[vertices];
this.parent = new int[vertices];
this.articulatePoints = new int[vertices];
this.lowestAdj = new int[vertices];
this.distance = new int[vertices];
this.initialize();
}

private void initialize(){
for(int i = 0 ; i < this.vertices ; i++){
graph[i] = new LinkedList<Integer>();
}
}

public void addEdge(int u , int v){
graph[u].add(v);
graph[v].add(u);
}

private void articulateUtil(int u){

int children  = 0 ;

this.visited[u] = 1;

this.distance[u] = this.lowestAdj[u] = ++time;

Iterator<Integer> items = this.graph[u].iterator();

while(items.hasNext()){

int item = items.next();

if(this.visited[item] == 0){
children++;
this.parent[item] = u;
articulateUtil(item);

lowestAdj[u] = Math.min(lowestAdj[u], lowestAdj[item]);

//we need to find two conditions one for parent and another for back edge

if(parent[u] == NIL && children > 1){
this.articulatePoints[u] = 1;
}
else if(this.parent[u] != NIL && this.distance[u] <= this.lowestAdj[item]){
this.articulatePoints[u] = 1;
}

}

else if( item != parent[u] ){
lowestAdj[u] = Math.min(distance[item], lowestAdj[u]);
}
}



}

public void findArticulatePoint(){

for(int i = 0 ; i < this.vertices ; i++){
this.parent[i] = NIL;
}
for(int i = 0 ; i < this.vertices ; i++){
if(this.visited[i] == 0){
this.articulateUtil(i);
}
}
for(int i = 0 ; i < this.vertices ; i++){
if(this.articulatePoints[i] == 1){
System.out.println("This is articulate points " + i);
}
}
}

public static void main(String [] args){
        Graph graph = new Graph(5);
        graph.addEdge(1, 0);
        graph.addEdge(0, 2);
        graph.addEdge(2, 1);
        graph.addEdge(0, 3);
        graph.addEdge(3, 4);
        graph.findArticulatePoint();

}

}

Reference :- http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/