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/AutoComplete.java at master · rp-code9/programming

Expand file tree

/

AutoComplete.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
122 lines (102 loc) · 3.19 KB
/

AutoComplete.java

Copy path

File metadata and controls

122 lines (102 loc) · 3.19 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*
* Problem : https://www.geeksforgeeks.org/auto-complete-feature-using-trie/
*/
import java.util.List;
import java.util.LinkedList;
public class AutoComplete {
private static final int R = 26;
private Node root;
private static class Node {
boolean isEndOfWord;
Node[] next;
public Node() {
next = new Node[R];
for (int i = 0; i < R; ++i) {
next[i] = null;
}
isEndOfWord = false;
}
}
public AutoComplete() {
root = new Node();
}
private int getIndex(char c) {
return (int)c - 'a';
}
public void insert(String key) {
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.isEndOfWord = true;
}
private boolean isTerminalNode(Node node) {
for (int i = 0; i < node.next.length; ++i) {
if (node.next[i] != null) {
return false;
}
}
return true;
}
private void searchRec(Node node, String prefix, List<String> list) {
if (node.isEndOfWord) {
list.add(prefix);
}
if (isTerminalNode(node)) {
return;
}
for (int i = 0; i < node.next.length; ++i) {
if (node.next[i] != null) {
char c = (char)('a' + i);
searchRec(node.next[i], prefix + c, list);
}
}
}
private List search(String key) {
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) {
return null;
}
temp = temp.next[index];
}
List<String> list = new LinkedList<String>();
// If this prefix is in last node of tree
if (temp.isEndOfWord && isTerminalNode(temp)) {
list.add(key);
} else if (!isTerminalNode(temp)) {
// There are more nodes below this node
String prefix = key;
searchRec(temp, prefix, list);
}
return list;
}
public static void main(String[] args) {
String[] words = {"geeks", "for", "geeks", "a", "portal",
"to", "learn", "can", "be", "computer",
"science", "zoom", "yup", "fire", "in", "data", "hell",
"hello", "helping", "hel", "help", "helps", "helping"};
AutoComplete auto = new AutoComplete();
for (int i = 0; i < words.length; ++i) {
auto.insert(words[i]);
}
String prefix = "a";
List<String> list = auto.search(prefix);
if (list == null || list.size() == 0) {
System.out.println("No words found for " + prefix);
} else {
System.out.println("Words found for " + prefix + " " + list);
}
}
}
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.