GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — programming/problems/string/SortStringUsingTrie.java at master · rp-code9/programming

Expand file tree

/

SortStringUsingTrie.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
89 lines (76 loc) · 2.42 KB
/

SortStringUsingTrie.java

Copy path

File metadata and controls

89 lines (76 loc) · 2.42 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
* Problem : https://www.geeksforgeeks.org/sorting-array-strings-words-using-trie/
*/
import java.util.List;
import java.util.LinkedList;
// Assumption is that all characters are lower case
public class SortStringUsingTrie {
private static final int R = 26;
private Node root;
private static class Node {
int index;
Node[] next;
public Node() {
next = new Node[R];
for (int i = 0; i < 26; ++i) {
next[i] = null;
}
index = -1;
}
}
public SortStringUsingTrie() {
root = new Node();
}
private static int getIndex(char c) {
return (int)c - 'a';
}
public void insert(String key, int keyIndex) {
if (key == null) {
throw new IllegalArgumentException();
}
Node temp = root;
for (int i = 0; i < key.length(); ++i) {
int index = getIndex(key.charAt(i));
if (temp.next[index] == null) {
temp.next[index] = new Node();
}
temp = temp.next[index];
}
temp.index = keyIndex;
}
private void preorder(Node node, String[] array, List<String> sorted) {
if (node == null) {
return;
}
for (int i = 0; i < R; ++i) {
if (node.next[i] != null) {
if (node.next[i].index != -1) {
sorted.add(array[node.next[i].index]);
}
preorder(node.next[i], array, sorted);
}
}
}
public List<String> sort(String[] array) {
List<String> sorted = new LinkedList<>();
preorder(root, array, sorted);
return sorted;
}
public static void main(String[] args) {
String[] array = {"geeks", "for", "geeks", "a", "portal",
"to", "learn", "can", "be", "computer",
"science", "zoom", "yup", "fire", "in", "data"};
System.out.println("Before sorting: ");
for (int i = 0; i < array.length; ++i) {
System.out.print(array[i] + " ");
}
System.out.println();
SortStringUsingTrie trie = new SortStringUsingTrie();
for (int i = 0; i < array.length; ++i) {
trie.insert(array[i], i);
}
List<String> sorted = trie.sort(array);
System.out.println("After sorting: ");
System.out.println(sorted);
}
}
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.