Skip to content

Commit 33e5ec9

Browse files
amangit1314amangit1314
committed
modify: #Modification 144
1 parent fa3c5ef commit 33e5ec9

35 files changed

Lines changed: 116 additions & 105 deletions

‎Test.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
import javax.swing.*;
22

33
public class Test {
4+
@SuppressWarnings("deprecation")
45
public static void main(String[] args) {
56
JFrame f = new JFrame("Test");
67
JButton b = new JButton("🚩");

‎backtracking/Max_possible_no_by_doing_atmost_k_swaps.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
package backtracking;
2-
import java.util.*;
2+
33
public class Max_possible_no_by_doing_atmost_k_swaps {
44
static String strMax = "";
55

‎backtracking/Nth_Root_of_M.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ public static double getNthRoot(int n, int m) {
4040
public static void main(String[] args) {
4141
Scanner sc = new Scanner(System.in);
4242
int n = sc.nextInt(), m = sc.nextInt();
43+
sc.close();
4344
System.out.print(getNthRoot(n, m));
4445
}
4546
}

‎backtracking/Path_more_than_k.java‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,8 @@ boolean pathMoreThanKUtil(int src, int k, boolean[] path) {
4545
if(k <= 0)
4646
return true;
4747

48-
ArrayList<AdjListNode> it = adj.get(src);
48+
adj.get(src);
49+
@SuppressWarnings("unused")
4950
int index = 0;
5051

5152
for(int i = 0; i < adj.get(src).size(); i++) {
@@ -72,7 +73,7 @@ boolean pathMoreThanKUtil(int src, int k, boolean[] path) {
7273
}
7374

7475
public static void main(String[] args) {
75-
int v = 1;
76-
Graph g = new Graph(v);
76+
// int v = 1;
77+
// Graph g = new Graph(v);
7778
}
7879
}

‎backtracking/Print_All_Palindrome_Partitions.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,7 @@ public static void main(String[] args) {
6464
// Taking string as input
6565
Scanner sc = new Scanner(System.in);
6666
String input = sc.nextLine();
67+
sc.close();
6768

6869
//finding the result for
6970
System.out.println("All possible palindrome partitions for " + input + " are :");

‎backtracking/Print_All_Permutations.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ public static void main(String[] args) {
4343
// Asking user for String str as input
4444
String str = sc.nextLine();
4545
int n = str.length();
46+
sc.close();
4647

4748
// Making an object of Print_All_Permutations class
4849
Print_All_Permutations permutation = new Print_All_Permutations();

‎backtracking/Print_all_Permutations_of_string.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
package backtracking;
2-
import java.util.*;
2+
33

44
public class Print_all_Permutations_of_string {
55

‎backtracking/RemoveInvalidParenthesis.java‎

Lines changed: 64 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -5,76 +5,75 @@
55
// Problem Title => Remove Invalid Parenthesis
66
public class RemoveInvalidParenthesis {
77

8-
// check if character parenthesis (is open or close)
9-
static boolean isParenthesis(char c){
10-
return ((c == '(') || (c == ')'));
8+
// check if character parenthesis (is open or close)
9+
static boolean isParenthesis(char c) {
10+
return ((c == '(') || (c == ')'));
11+
}
12+
13+
static boolean isValidString(String str) {
14+
int count = 0;
15+
for (int i = 0; i < str.length(); i++) {
16+
if (str.charAt(i) == '(')
17+
count++;
18+
else if (str.charAt(i) == ')')
19+
count--;
20+
if (count < 0)
21+
return false;
1122
}
23+
return (count == 0);
24+
}
25+
26+
// Method to remove invalid parenthesis (without using HashSet)
27+
static void removeInvalidParenthesis(String str) {
28+
if (str.isEmpty()) return;
29+
30+
Queue<String> q = new LinkedList<>();
31+
String temp;
32+
33+
// Pushing given string as starting node into queue
34+
q.add(str);
35+
36+
int level = 0; // To track level for processing only valid strings of current level
37+
boolean foundValid = false; // Flag to indicate if a valid string was found
38+
39+
while (!q.isEmpty()) {
40+
int size = q.size(); // Process all strings of current level
41+
42+
for (int i = 0; i < size; i++) {
43+
str = q.poll();
1244

13-
static boolean isValidString(String str){
14-
int count = 0;
15-
for(int i = 0; i < str.length(); i++){
16-
if(str.charAt(i) == '(')
17-
count++;
18-
else if(str.charAt(i) == ')')
19-
count--;
20-
if(count < 0)
21-
return false;
45+
if (isValidString(str)) {
46+
System.out.println(str);
47+
foundValid = true;
2248
}
23-
return (count == 0);
24-
}
2549

26-
// Method to remove invalid parenthesis
27-
static void removeInvalidParenthesis(String str){
28-
if(str.isEmpty())
29-
return;
30-
31-
// visit set to ignore already visited string
32-
HashSet<String> visit = new HashSet<>();
33-
34-
// queue to maintain BFS
35-
Queue<String> q = new LinkedList<>();String temp;
36-
boolean level = false;
37-
38-
// pushing given string as
39-
// starting node into queue
40-
q.add(str);
41-
visit.add(str);
42-
while (!q.isEmpty())
43-
{
44-
str = q.peek(); q.remove();
45-
if (isValidString(str))
46-
{
47-
System.out.println(str);
48-
49-
// If answer is found, make level true
50-
// so that valid string of only that level
51-
// are processed.
52-
level = true;
53-
}
54-
if (level)
55-
continue;
56-
for (int i = 0; i < str.length(); i++)
57-
{
58-
if (!isParenthesis(str.charAt(i)))
59-
continue;
60-
61-
// Removing parenthesis from str and
62-
// pushing into queue,if not visited already
63-
temp = str.substring(0, i) + str.substring(i + 1);
64-
if (!visit.contains(temp)) {
65-
q.add(temp);
66-
visit.add(temp);
67-
}
68-
}
50+
// If a valid string is found at the current level, skip processing further strings
51+
// at this level (optimization)
52+
if (foundValid && level > 0) {
53+
continue;
6954
}
70-
}
7155

72-
public static void main(String[] args) {
73-
Scanner sc = new Scanner(System.in);
74-
String expression = sc.nextLine();
75-
removeInvalidParenthesis(expression);
56+
for (int j = 0; j < str.length(); j++) {
57+
if (!isParenthesis(str.charAt(j))) continue;
58+
59+
// Removing parenthesis from str and pushing into queue
60+
temp = str.substring(0, j) + str.substring(j + 1);
61+
q.add(temp);
62+
}
63+
}
7664

77-
expression = "()v)";
78-
removeInvalidParenthesis(expression);
65+
level++; // Move to next level (indicates processing children of current level strings)
66+
foundValid = false; // Reset flag for next level
7967
}
80-
}
68+
}
69+
70+
public static void main(String[] args) {
71+
Scanner sc = new Scanner(System.in);
72+
String expression = sc.nextLine();
73+
removeInvalidParenthesis(expression);
74+
sc.close();
75+
76+
expression = "()v)";
77+
removeInvalidParenthesis(expression);
78+
}
79+
}

‎backtracking/Word_Break_PUB.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -31,9 +31,9 @@ public static void main(String[] args) {
3131

3232
String sentence = "I Like mango icecream and SamSung Mobile";
3333
String A = null;
34-
String[] result;
35-
String[] dictionary = {"mobile", "samsung", "sam", "sung", "man", "mango", "icecream", "and", "go", "i", "like",
36-
"icecream"};
34+
// String[] result;
35+
// String[] dictionary = {"mobile", "samsung", "sam", "sung", "man", "mango", "icecream", "and", "go", "i", "like",
36+
// "icecream"};
3737

3838
System.out.println(wordBreak(A,sentence));
3939
}

‎miscellaneous/First_Last_Occurrence.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,12 +6,12 @@
66
public class First_Last_Occurrence {
77

88
// This function will return first index of element
9-
public static int first(ArrayList list, int x){
9+
public static int first(ArrayList<Integer> list, int x){
1010
return list.indexOf(x);
1111
}
1212

1313
// This function will return last index of element
14-
public static int last(ArrayList list, int x){
14+
public static int last(ArrayList<Integer> list, int x){
1515
return list.lastIndexOf(x);
1616
}
1717

0 commit comments

Comments
 (0)