#practiceLinkDiv { display: none !important; }Adott egy listát a telefonkönyvben található kapcsolatokról. A feladat egy keresési lekérdezés megvalósítása a telefonkönyvhöz. A keresési lekérdezés egy karakterláncon str " megjeleníti az összes névjegyet, amelyek előtagja " str '. A keresési funkció egyik speciális tulajdonsága, hogy amikor a felhasználó keres egy névjegyet a névjegyzékből, akkor javaslatok jelennek meg (a névjegyek előtaggal, mint a megadott karakterlánc), miután a felhasználó beírja az egyes karaktereket.
Jegyzet: A listában szereplő névjegyek csak kisbetűket tartalmaznak. Példa:
obj java-ban
Input : contacts [] = {gforgeeks geeksquiz } Query String = gekk Output : Suggestions based on 'g' are geeksquiz gforgeeks Suggestions based on 'ge' are geeksquiz No Results Found for 'gek' No Results Found for 'gekk' Javasolt: Kérjük, oldja meg GYAKORLAT először, mielőtt rátérnénk a megoldásra.
A Phone Directory segítségével hatékonyan megvalósítható Trie Adatstruktúra. Az összes érintkezőt beillesztjük a Trie-be. Általában a keresési lekérdezés egy Trie-n annak megállapítására szolgál, hogy a karakterlánc jelen van-e a trie-ben, de ebben az esetben meg kell találnunk az összes karakterláncot, amelyek mindegyike „str” előtaggal rendelkezik. Ez egyenértékű az a DFS bejárás grafikonon . Egy Trie csomópontból keresse fel a szomszédos Trie csomópontokat, és tegye ezt rekurzív módon, amíg nincs több szomszédos. Ez a rekurzív függvény 2 argumentumot vesz fel, egyet Trie Node-ként, amely az aktuális Trie-csomópontra mutat, a másikat pedig olyan karakterláncként, amely az eddig talált karakterláncot tárolja „str” előtaggal. Minden Trie Node tárol egy logikai változót „isLast”, amely akkor igaz, ha a csomópont egy kapcsolat (szó) végét jelenti.
// This function displays all words with given // prefix. 'node' represents last node when // path from root follows characters of 'prefix'. displayContacts (TreiNode node string prefix) If (node.isLast is true) display prefix // finding adjacent nodes for each character ‘i’ in lower case Alphabets if (node.child[i] != NULL) displayContacts(node.child[i] prefix+i)
A felhasználó karakterenként írja be a sztringet, és minden beírt karakter után meg kell jelenítenünk a javaslatokat az előtaggal. Tehát az egyik módszer a kialakított karakterlánccal kezdődő előtag megkeresésére az, hogy ellenőrizzük, hogy az előtag létezik-e a Trie-ben, ha igen, akkor hívjuk meg a displayContacts() függvényt. Ebben a megközelítésben minden beírt karakter után ellenőrizzük, hogy a karakterlánc létezik-e a Trie-ben. Ahelyett, hogy újra és újra ellenőriznénk, fenntarthatunk egy mutatót prevNode ', amely a felhasználó által utoljára beírt karakternek megfelelő TrieNode-ra mutat, most ellenőriznünk kell a gyermekcsomópontot a 'prevNode' számára, amikor a felhasználó egy másik karaktert ír be, hogy ellenőrizze, hogy az létezik-e a Trie-ben. Ha az új előtag nincs a Trie-ben, akkor az összes karakterlánc, amely az „előtag” utáni karakterek beírásával jön létre, a Trie-ben sem található meg. Tehát megtörjük az előtagok generálására használt hurkot egyenként, és kinyomtatjuk a „Nincs eredmény” szöveget az összes fennmaradó karakterhez.
C++
// C++ Program to Implement a Phone // Directory Using Trie Data Structure #include
// Java Program to Implement a Phone // Directory Using Trie Data Structure import java.util.*; class TrieNode { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. HashMap<CharacterTrieNode> child; // 'isLast' is true if the node represents // end of a contact boolean isLast; // Default Constructor public TrieNode() { child = new HashMap<CharacterTrieNode>(); // Initialize all the Trie nodes with NULL for (char i = 'a'; i <= 'z'; i++) child.put(inull); isLast = false; } } class Trie { TrieNode root; // Insert all the Contacts into the Trie public void insertIntoTrie(String contacts[]) { root = new TrieNode(); int n = contacts.length; for (int i = 0; i < n; i++) { insert(contacts[i]); } } // Insert a Contact into the Trie public void insert(String s) { int len = s.length(); // 'itr' is used to iterate the Trie Nodes TrieNode itr = root; for (int i = 0; i < len; i++) { // Check if the s[i] is already present in // Trie TrieNode nextNode = itr.child.get(s.charAt(i)); if (nextNode == null) { // If not found then create a new TrieNode nextNode = new TrieNode(); // Insert into the HashMap itr.child.put(s.charAt(i)nextNode); } // Move the iterator('itr') to point to next // Trie Node itr = nextNode; // If its the last character of the string 's' // then mark 'isLast' as true if (i == len - 1) itr.isLast = true; } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. public void displayContactsUtil(TrieNode curNode String prefix) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if (curNode.isLast) System.out.println(prefix); // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for (char i = 'a'; i <= 'z'; i++) { TrieNode nextNode = curNode.child.get(i); if (nextNode != null) { displayContactsUtil(nextNode prefix + i); } } } // Display suggestions after every character enter by // the user for a given string 'str' void displayContacts(String str) { TrieNode prevNode = root; // 'flag' denotes whether the string entered // so far is present in the Contact List String prefix = ''; int len = str.length(); // Display the contact List for string formed // after entering every character int i; for (i = 0; i < len; i++) { // 'str' stores the string entered so far prefix += str.charAt(i); // Get the last character entered char lastChar = prefix.charAt(i); // Find the Node corresponding to the last // character of 'str' which is pointed by // prevNode of the Trie TrieNode curNode = prevNode.child.get(lastChar); // If nothing found then break the loop as // no more prefixes are going to be present. if (curNode == null) { System.out.println('nNo Results Found for ' + prefix); i++; break; } // If present in trie then display all // the contacts with given prefix. System.out.println('nSuggestions based on ' + prefix + ' are '); displayContactsUtil(curNode prefix); // Change prevNode for next prefix prevNode = curNode; } for ( ; i < len; i++) { prefix += str.charAt(i); System.out.println('nNo Results Found for ' + prefix); } } } // Driver code class Main { public static void main(String args[]) { Trie trie = new Trie(); String contacts [] = {'gforgeeks' 'geeksquiz'}; trie.insertIntoTrie(contacts); String query = 'gekk'; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' trie.displayContacts(query); } }
# Python Program to Implement a Phone # Directory Using Trie Data Structure class TrieNode: def __init__(self): # Each Trie Node contains a Map 'child' # where each alphabet points to a Trie # Node. self.child = {} self.is_last = False # Making root NULL for ease so that it doesn't # have to be passed to all functions. root = TrieNode() # Insert a Contact into the Trie def insert(string): # 'itr' is used to iterate the Trie Nodes itr = root for char in string: # Check if the s[i] is already present in # Trie if char not in itr.child: # If not found then create a new TrieNode itr.child[char] = TrieNode() # Move the iterator('itr') to point to next # Trie Node itr = itr.child[char] # If its the last character of the string 's' # then mark 'isLast' as true itr.is_last = True # This function simply displays all dictionary words # going through current node. String 'prefix' # represents string corresponding to the path from # root to curNode. def display_contacts_util(cur_node prefix): # Check if the string 'prefix' ends at this Node # If yes then display the string found so far if cur_node.is_last: print(prefix) # Find all the adjacent Nodes to the current # Node and then call the function recursively # This is similar to performing DFS on a graph for i in range(ord('a') ord('z') + 1): char = chr(i) next_node = cur_node.child.get(char) if next_node: display_contacts_util(next_node prefix + char) # Display suggestions after every character enter by # the user for a given query string 'str' def displayContacts(string): prev_node = root prefix = '' # Display the contact List for string formed # after entering every character for i char in enumerate(string): # 'prefix' stores the string formed so far prefix += char # Find the Node corresponding to the last # character of 'prefix' which is pointed by # prevNode of the Trie cur_node = prev_node.child.get(char) # If nothing found then break the loop as # no more prefixes are going to be present. if not cur_node: print(f'No Results Found for {prefix}n') break # If present in trie then display all # the contacts with given prefix. print(f'Suggestions based on {prefix} are 'end=' ') display_contacts_util(cur_node prefix) print() # Change prevNode for next prefix prev_node = cur_node # Once search fails for a prefix we print # 'Not Results Found' for all remaining # characters of current query string 'str'. for char in string[i+1:]: prefix += char print(f'No Results Found for {prefix}n') # Insert all the Contacts into the Trie def insertIntoTrie(contacts): # Insert each contact into the trie for contact in contacts: insert(contact) # Driver program to test above functions # Contact list of the User contacts=['gforgeeks''geeksquiz'] # Size of the Contact List n=len(contacts) # Insert all the Contacts into Trie insertIntoTrie(contacts) query = 'gekk' # Note that the user will enter 'g' then 'e' so # first display all the strings with prefix as 'g' # and then all the strings with prefix as 'ge' displayContacts(query) # This code is contributed by Aman Kumar
// C# Program to Implement a Phone // Directory Using Trie Data Structure using System; using System.Collections.Generic; class TrieNode { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. public Dictionary<char TrieNode> child; // 'isLast' is true if the node represents // end of a contact public bool isLast; // Default Constructor public TrieNode() { child = new Dictionary<char TrieNode>(); // Initialize all the Trie nodes with NULL for (char i = 'a'; i <= 'z'; i++) child.Add(i null); isLast = false; } } class Trie { public TrieNode root; // Insert all the Contacts into the Trie public void insertIntoTrie(String []contacts) { root = new TrieNode(); int n = contacts.Length; for (int i = 0; i < n; i++) { insert(contacts[i]); } } // Insert a Contact into the Trie public void insert(String s) { int len = s.Length; // 'itr' is used to iterate the Trie Nodes TrieNode itr = root; for (int i = 0; i < len; i++) { // Check if the s[i] is already present in // Trie TrieNode nextNode = itr.child[s[i]]; if (nextNode == null) { // If not found then create a new TrieNode nextNode = new TrieNode(); // Insert into the Dictionary if(itr.child.ContainsKey(s[i])) itr.child[s[i]] = nextNode; else itr.child.Add(s[i] nextNode); } // Move the iterator('itr') to point to next // Trie Node itr = nextNode; // If its the last character of the string 's' // then mark 'isLast' as true if (i == len - 1) itr.isLast = true; } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. public void displayContactsUtil(TrieNode curNode String prefix) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if (curNode.isLast) Console.WriteLine(prefix); // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for (char i = 'a'; i <= 'z'; i++) { TrieNode nextNode = curNode.child[i]; if (nextNode != null) { displayContactsUtil(nextNode prefix + i); } } } // Display suggestions after every character enter by // the user for a given string 'str' public void displayContacts(String str) { TrieNode prevNode = root; // 'flag' denotes whether the string entered // so far is present in the Contact List String prefix = ''; int len = str.Length; // Display the contact List for string formed // after entering every character int i; for (i = 0; i < len; i++) { // 'str' stores the string entered so far prefix += str[i]; // Get the last character entered char lastChar = prefix[i]; // Find the Node corresponding to the last // character of 'str' which is pointed by // prevNode of the Trie TrieNode curNode = prevNode.child[lastChar]; // If nothing found then break the loop as // no more prefixes are going to be present. if (curNode == null) { Console.WriteLine('nNo Results Found for ' + prefix); i++; break; } // If present in trie then display all // the contacts with given prefix. Console.WriteLine('nSuggestions based on ' + prefix + ' are '); displayContactsUtil(curNode prefix); // Change prevNode for next prefix prevNode = curNode; } for ( ; i < len; i++) { prefix += str[i]; Console.WriteLine('nNo Results Found for ' + prefix); } } } // Driver code public class GFG { public static void Main(String []args) { Trie trie = new Trie(); String []contacts = {'gforgeeks' 'geeksquiz'}; trie.insertIntoTrie(contacts); String query = 'gekk'; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' trie.displayContacts(query); } } // This code is contributed by PrinciRaj1992
<script> // Javascript Program to Implement a Phone // Directory Using Trie Data Structure class TrieNode { constructor() { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. // We can also use a fixed size array of // size 256. this.child = {}; // 'isLast' is true if the node represents // end of a contact this.isLast = false; } } // Making root NULL for ease so that it doesn't // have to be passed to all functions. let root = null; // Insert a Contact into the Trie function insert(s) { const len = s.length; // 'itr' is used to iterate the Trie Nodes let itr = root; for (let i = 0; i < len; i++) { // Check if the s[i] is already present in // Trie const char = s[i]; let nextNode = itr.child[char]; if (nextNode === undefined) { // If not found then create a new TrieNode nextNode = new TrieNode(); // Insert into the Map itr.child[char] = nextNode; } // Move the iterator('itr') to point to next // Trie Node itr = nextNode; // If its the last character of the string 's' // then mark 'isLast' as true if (i === len - 1) { itr.isLast = true; } } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. function displayContactsUtil(curNode prefix) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if (curNode.isLast) { document.write(prefix+'
'); } // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for (let i = 97; i <= 122; i++) { const char = String.fromCharCode(i); const nextNode = curNode.child[char]; if (nextNode !== undefined) { displayContactsUtil(nextNode prefix + char); } } } // Display suggestions after every character enter by // the user for a given query string 'str' function displayContacts(str) { let prevNode = root; let prefix = ''; const len = str.length; // Display the contact List for string formed // after entering every character let i; for (i = 0; i < len; i++) { // 'prefix' stores the string formed so far prefix += str[i]; // Get the last character entered const lastChar = prefix[i]; // Find the Node corresponding to the last // character of 'prefix' which is pointed by // prevNode of the Trie const curNode = prevNode.child[lastChar]; // If nothing found then break the loop as // no more prefixes are going to be present. if (curNode === undefined) { document.write(`No Results Found for ${prefix}`+'
'); i++; break; } // If present in trie then display all // the contacts with given prefix. document.write(`Suggestions based on ${prefix} are `); displayContactsUtil(curNode prefix); document.write('
'); // Change prevNode for next prefix prevNode = curNode; } document.write('
'); // Once search fails for a prefix we print // 'Not Results Found' for all remaining // characters of current query string 'str'. for (; i < len; i++) { prefix += str[i]; document.write('No Results Found for ' + prefix + '
'); } } // Insert all the Contacts into the Trie function insertIntoTrie(contacts) { // Initialize root Node root = new TrieNode(); const n = contacts.length; // Insert each contact into the trie for (let i = 0; i < n; i++) { insert(contacts[i]); } } // Driver program to test above functions // Contact list of the User const contacts = ['gforgeeks' 'geeksquiz']; //Insert all the Contacts into Trie insertIntoTrie(contacts); const query = 'gekk'; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' displayContacts(query); // This code is contributed by Utkarsh Kumar. </script>
Kimenet
Suggestions based on gare geeksquiz gforgeeks Suggestions based on geare geeksquiz No Results Found for gek No Results Found for gekk
Időbonyolultság: O(n*m), ahol n az érintkezők száma, m pedig egy kapcsolati karakterlánc maximális hossza.
Segédtér: O(n*m)