Dado un diccionario de palabras y una string de entrada, encuentre el prefijo más largo de la string que también es una palabra en el diccionario.
Ejemplos:
Let the dictionary contains the following words: {are, area, base, cat, cater, children, basement} Below are some input/output examples: -------------------------------------- Input String Output -------------------------------------- caterer cater basemexy base child < Empty >
Solución
Construimos un Trie de todas las palabras del diccionario. Una vez que se construye el Trie, recorra a través de él usando los caracteres de la string de entrada. Si el prefijo coincide con una palabra del diccionario, almacene la longitud actual y busque una coincidencia más larga. Finalmente, devuelve la coincidencia más larga.
A continuación se muestra la implementación de Java de la solución anterior basada.
import java.util.HashMap; // Trie Node, which stores a character and the children in a HashMap class TrieNode { public TrieNode(char ch) { value = ch; children = new HashMap<>(); bIsEnd = false; } public HashMap<Character,TrieNode> getChildren() { return children; } public char getValue() { return value; } public void setIsEnd(boolean val) { bIsEnd = val; } public boolean isEnd() { return bIsEnd; } private char value; private HashMap<Character,TrieNode> children; private boolean bIsEnd; } // Implements the actual Trie class Trie { // Constructor public Trie() { root = new TrieNode((char)0); } // Method to insert a new word to Trie public void insert(String word) { // Find length of the given word int length = word.length(); TrieNode crawl = root; // Traverse through all characters of given word for( int level = 0; level < length; level++) { HashMap<Character,TrieNode> child = crawl.getChildren(); char ch = word.charAt(level); // If there is already a child for current character of given word if( child.containsKey(ch)) crawl = child.get(ch); else // Else create a child { TrieNode temp = new TrieNode(ch); child.put( ch, temp ); crawl = temp; } } // Set bIsEnd true for last character crawl.setIsEnd(true); } // The main method that finds out the longest string 'input' public String getMatchingPrefix(String input) { String result = ""; // Initialize resultant string int length = input.length(); // Find length of the input string // Initialize reference to traverse through Trie TrieNode crawl = root; // Iterate through all characters of input string 'str' and traverse // down the Trie int level, prevMatch = 0; for( level = 0 ; level < length; level++ ) { // Find current character of str char ch = input.charAt(level); // HashMap of current Trie node to traverse down HashMap<Character,TrieNode> child = crawl.getChildren(); // See if there is a Trie edge for the current character if( child.containsKey(ch) ) { result += ch; //Update result crawl = child.get(ch); //Update crawl to move down in Trie // If this is end of a word, then update prevMatch if( crawl.isEnd() ) prevMatch = level + 1; } else break; } // If the last processed character did not match end of a word, // return the previously matching prefix if( !crawl.isEnd() ) return result.substring(0, prevMatch); else return result; } private TrieNode root; } // Testing class public class Test { public static void main(String[] args) { Trie dict = new Trie(); dict.insert("are"); dict.insert("area"); dict.insert("base"); dict.insert("cat"); dict.insert("cater"); dict.insert("basement"); String input = "caterer"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); input = "basement"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); input = "are"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); input = "arex"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); input = "basemexz"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); input = "xyz"; System.out.print(input + ": "); System.out.println(dict.getMatchingPrefix(input)); } }
Producción:
caterer: cater basement: basement are: are arex: are basemexz: base xyz:
Complejidad de tiempo: la complejidad de tiempo para encontrar el prefijo más largo es O (n), donde n es la longitud de la string de entrada. Consulte esto para conocer la complejidad del tiempo de construcción del Trie.
Este artículo ha sido compilado por Ravi Chandra Enaganti . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA