Skip to content

Commit 7cc96f9

Browse files
ritweekraj2802ritweekraj2802
authored
Add multiple algorithms (TheAlgorithms#2442)
1 parent 654aec9 commit 7cc96f9

3 files changed

Lines changed: 408 additions & 0 deletions

File tree

‎Others/Implementing_auto_completing_features_using_trie.java‎

Lines changed: 183 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,183 @@
1+
package Others;
2+
3+
4+
// Java Program to implement Auto-Complete
5+
// Feature using Trie
6+
7+
import java.util.*;
8+
import java.io.*;
9+
import java.lang.*;
10+
11+
class Trieac {
12+
13+
// Alphabet size (# of symbols)
14+
public static final int ALPHABET_SIZE = 26;
15+
16+
// Trie node
17+
static class TrieNode
18+
{
19+
TrieNode children[] = new TrieNode[ALPHABET_SIZE];
20+
21+
// isWordEnd is true if the node represents
22+
// end of a word
23+
boolean isWordEnd;
24+
};
25+
26+
// Returns new trie node (initialized to NULLs)
27+
static TrieNode getNode() {
28+
TrieNode pNode = new TrieNode();
29+
pNode.isWordEnd = false;
30+
31+
for(int i = 0; i < ALPHABET_SIZE; i++)
32+
pNode.children[i] = null;
33+
34+
return pNode;
35+
}
36+
37+
// If not present, inserts key into trie. If the
38+
// key is prefix of trie node, just marks leaf node
39+
static void insert(TrieNode root, final String key)
40+
{
41+
TrieNode pCrawl = root;
42+
43+
for(int level = 0; level < key.length(); level++)
44+
{
45+
int index = (key.charAt(level) - 'a');
46+
if (pCrawl.children[index] == null)
47+
pCrawl.children[index] = getNode();
48+
pCrawl = pCrawl.children[index];
49+
}
50+
51+
// mark last node as leaf
52+
pCrawl.isWordEnd = true;
53+
}
54+
55+
// Returns true if key presents in trie, else false
56+
boolean search(TrieNode root, final String key)
57+
{
58+
int length = key.length();
59+
TrieNode pCrawl = root;
60+
61+
for (int level = 0; level < length; level++)
62+
{
63+
int index = (key.charAt(level) - 'a');
64+
65+
if (pCrawl.children[index] == null)
66+
pCrawl = pCrawl.children[index];
67+
}
68+
69+
return (pCrawl != null && pCrawl.isWordEnd);
70+
}
71+
72+
// Returns 0 if current node has a child
73+
// If all children are NULL, return 1.
74+
static boolean isLastNode(TrieNode root)
75+
{
76+
for (int i = 0; i < ALPHABET_SIZE; i++)
77+
if (root.children[i] != null)
78+
return false;
79+
return true;
80+
}
81+
82+
// Recursive function to print auto-suggestions
83+
// for given node.
84+
static void suggestionsRec(TrieNode root, String currPrefix)
85+
{
86+
// found a string in Trie with the given prefix
87+
if (root.isWordEnd)
88+
{
89+
System.out.println(currPrefix);
90+
}
91+
92+
// All children struct node pointers are NULL
93+
if (isLastNode(root))
94+
return;
95+
96+
for (int i = 0; i < ALPHABET_SIZE; i++)
97+
{
98+
if (root.children[i] != null)
99+
{
100+
// append current character to currPrefix string
101+
currPrefix += (char)(97 + i);
102+
103+
// recur over the rest
104+
suggestionsRec(root.children[i], currPrefix);
105+
}
106+
}
107+
}
108+
109+
// Fucntion to print suggestions for
110+
// given query prefix.
111+
static int printAutoSuggestions(TrieNode root,
112+
final String query)
113+
{
114+
TrieNode pCrawl = root;
115+
116+
// Check if prefix is present and find the
117+
// the node (of last level) with last character
118+
// of given string.
119+
int level;
120+
int n = query.length();
121+
122+
for (level = 0; level < n; level++)
123+
{
124+
int index = (query.charAt(level) - 'a');
125+
126+
// no string in the Trie has this prefix
127+
if (pCrawl.children[index] == null)
128+
return 0;
129+
130+
pCrawl = pCrawl.children[index];
131+
}
132+
133+
// If prefix is present as a word.
134+
boolean isWord = (pCrawl.isWordEnd == true);
135+
136+
// If prefix is last node of tree (has no
137+
// children)
138+
boolean isLast = isLastNode(pCrawl);
139+
140+
// If prefix is present as a word, but
141+
// there is no subtree below the last
142+
// matching node.
143+
if (isWord && isLast)
144+
{
145+
System.out.println(query);
146+
return -1;
147+
}
148+
149+
// If there are are nodes below last
150+
// matching character.
151+
if (!isLast)
152+
{
153+
String prefix = query;
154+
suggestionsRec(pCrawl, prefix);
155+
return 1;
156+
}
157+
158+
return 0;
159+
}
160+
161+
// Driver code
162+
public static void main(String[] args)
163+
{
164+
TrieNode root = getNode();
165+
insert(root, "hello");
166+
insert(root, "dog");
167+
insert(root, "hell");
168+
insert(root, "cat");
169+
insert(root, "a");
170+
insert(root, "hel");
171+
insert(root, "help");
172+
insert(root, "helps");
173+
insert(root, "helping");
174+
int comp = printAutoSuggestions(root, "hel");
175+
176+
if (comp == -1)
177+
System.out.println("No other strings found "+
178+
"with this prefix\n");
179+
else if (comp == 0)
180+
System.out.println("No string found with"+
181+
" this prefix\n");
182+
}
183+
}

‎Others/Sudoku.java‎

Lines changed: 159 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,159 @@
1+
package Others;
2+
3+
4+
class Sudoku
5+
{
6+
public static boolean isSafe(int[][] board,
7+
int row, int col,
8+
int num)
9+
{
10+
// Row has the unique (row-clash)
11+
for (int d = 0; d < board.length; d++)
12+
{
13+
14+
// Check if the number we are trying to
15+
// place is already present in
16+
// that row, return false;
17+
if (board[row][d] == num) {
18+
return false;
19+
}
20+
}
21+
22+
// Column has the unique numbers (column-clash)
23+
for (int r = 0; r < board.length; r++)
24+
{
25+
26+
// Check if the number
27+
// we are trying to
28+
// place is already present in
29+
// that column, return false;
30+
if (board[r][col] == num)
31+
{
32+
return false;
33+
}
34+
}
35+
36+
// Corresponding square has
37+
// unique number (box-clash)
38+
int sqrt = (int)Math.sqrt(board.length);
39+
int boxRowStart = row - row % sqrt;
40+
int boxColStart = col - col % sqrt;
41+
42+
for (int r = boxRowStart;
43+
r < boxRowStart + sqrt; r++)
44+
{
45+
for (int d = boxColStart;
46+
d < boxColStart + sqrt; d++)
47+
{
48+
if (board[r][d] == num)
49+
{
50+
return false;
51+
}
52+
}
53+
}
54+
55+
// if there is no clash, it's safe
56+
return true;
57+
}
58+
59+
public static boolean solveSudoku(
60+
int[][] board, int n)
61+
{
62+
int row = -1;
63+
int col = -1;
64+
boolean isEmpty = true;
65+
for (int i = 0; i < n; i++)
66+
{
67+
for (int j = 0; j < n; j++)
68+
{
69+
if (board[i][j] == 0)
70+
{
71+
row = i;
72+
col = j;
73+
74+
// We still have some remaining
75+
// missing values in Sudoku
76+
isEmpty = false;
77+
break;
78+
}
79+
}
80+
if (!isEmpty) {
81+
break;
82+
}
83+
}
84+
85+
// No empty space left
86+
if (isEmpty)
87+
{
88+
return true;
89+
}
90+
91+
// Else for each-row backtrack
92+
for (int num = 1; num <= n; num++)
93+
{
94+
if (isSafe(board, row, col, num))
95+
{
96+
board[row][col] = num;
97+
if (solveSudoku(board, n))
98+
{
99+
// print(board, n);
100+
return true;
101+
}
102+
else
103+
{
104+
// replace it
105+
board[row][col] = 0;
106+
}
107+
}
108+
}
109+
return false;
110+
}
111+
112+
public static void print(
113+
int[][] board, int N)
114+
{
115+
116+
// We got the answer, just print it
117+
for (int r = 0; r < N; r++)
118+
{
119+
for (int d = 0; d < N; d++)
120+
{
121+
System.out.print(board[r][d]);
122+
System.out.print(" ");
123+
}
124+
System.out.print("\n");
125+
126+
if ((r + 1) % (int)Math.sqrt(N) == 0)
127+
{
128+
System.out.print("");
129+
}
130+
}
131+
}
132+
133+
// Driver Code
134+
public static void main(String args[])
135+
{
136+
137+
int[][] board = new int[][] {
138+
{ 3, 0, 6, 5, 0, 8, 4, 0, 0 },
139+
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
140+
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
141+
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
142+
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
143+
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
144+
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
145+
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
146+
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 }
147+
};
148+
int N = board.length;
149+
150+
if (solveSudoku(board, N))
151+
{
152+
// print solution
153+
print(board, N);
154+
}
155+
else {
156+
System.out.println("No solution");
157+
}
158+
}
159+
}

0 commit comments

Comments
 (0)