Achar Palavra em Uma Trie

Programação Java
#1

Bem, eu tenho uma duvida sobre como efeturar uma busca. Eu tenho uma Árvore Trie, construida utilizando HashMap. Tenho o metodo de inserção e um metodo para falar se a String esta na Trie. Eu preciso construir agora, um metodo que me retorne uma String que se aproxime da palavra que foi buscada.

Ex: Se eu tiver na Trie a String goleiro e procurar pela String gol, eu tenho q retornar a String goleiro.
Se eu tiver na Trie a String goleiro_rogerio e pesquisar por goleiro, ele me retorne goleiro_rogerio.

A ideia é retornar uma palavra que contenha o mesmo prefixo. Alguém pode me ajudar?

import java.util.*;
 
public class Trie {
	
	// raiz da trie
	HashMap<Character, HashMap> root;
 
	// instancia da trie
	public Trie() {
	
		root = new HashMap<Character, HashMap>();
	
	}
 
	// inserção da string na trie
	public void add(String s) {

		HashMap<Character, HashMap> curr_node = root;

		for (int i = 0, n = s.length(); i < n; i++) {

			Character c = s.charAt(i);

			if (curr_node.containsKey(c))

				curr_node = curr_node.get(c);

			else {

				curr_node.put(c, new HashMap<Character, HashMap>());

				curr_node = curr_node.get(c);

			}

		}

		curr_node.put('\0', new HashMap<Character, HashMap>(0)); 

	}
	
 
	// verifica se a trie contem a string passada como parametro
	public boolean contains(String s) {
		
		HashMap<Character, HashMap> curr_node = root;
		
		for (int i = 0, n = s.length(); i < n; i++) {
		
			Character c = s.charAt(i);
			
			if (curr_node.containsKey(c))
			
				curr_node = curr_node.get(c);
			else
				
				return false;
		}
		
		if (curr_node.containsKey('\0'))

			return true;
		else
			
			return false;
}
 
}
#2

A classe String tem o método startsWith que pode te ajudar. Se não ajudar, aí você pode partir pra expressões regulares.

Só uma pergunta. O que é Trie?

#3

Trie é uma estrutura de dados do tipo árvore ordenada, que pode ser usada para armazenar um array associativo em que as chaves são normalmente cadeias de caracteres.
E a utilização do startswith nem ajudaria no caso! =/

#4

Se você já fez um diagrama de uma trie, vai ver que não é só uma palavra que você vai encontrar com um determinado prefixo - você provavelmente terá de fazer uma função recursiva para percorrer as palavras.

Por exemplo, vamos mostrar a sua trie com as palavras:

gol
goleiro
goles
goleiro_rogerio
goleiro_andre
futebol

Se passar g, ele deve retornar “gol”, “goleiro”, “goles”, “goleiro_rogerio”, “goleiro_andre”
Se passar “goleiro”, deve retornar “goleiro”, “goleiro_rogerio”, “goleiro_andre”

Como você está usando uma trie que decompõe em caracteres, você vai ter algumas expressões bem compridas.

Você sabe como percorrer um HashMap? Normalmente se faz assim:

for (Map.Entry<Character, HashMap> entry: map.entrySet()) {
    System.out.printf ("chave = %s, valor = %s\n", entry.getKey(), entry.getValue());
}
#5

Eu não sabia como percorrer o HashMap não. Mas então, a ideia é pegar uma delas… não importando qual! Pois como você mostrou, pode ter mais de uma String.
A parada é q ela esteja dentro da trie.

#6