CODEWITHSUNDEEP
javasearchhashmaptrie
Boris
Boris

Reputation: 402

Trie data structure and effective search in Java

I've got a task about data structure and efficient search. First input parameter is some big text file that contains strings, each line is a new string. Second input parameter is some prefix. The output is the shortest word found in that big file that starts with the given prefix. So, I used HashMap and built a Trie using each letter as a key. So, I make just a look up instead of iteration which saves time and memory. The only thing that looks not good for me is searching the shortest word. I mean now I get the list of words that start with the given prefix. And then I search the shortest one iterating through the list. Is there any other way to get the shortest word? Any suggestions how to make this better are really appreciated as this is the first time in my life I work with Trie. Please, see my code below:

TrieNode

class TrieNode {

HashMap<Character, TrieNode> child;

boolean isLast;

public TrieNode() {
    child = new HashMap<Character, TrieNode>();
    // Initialize all the Trie nodes with NULL
    for (char i = 'a'; i <= 'z'; i++)
        child.put(i, null);
    isLast = false;
}}

Trie

public class Trie {

TrieNode root = new TrieNode();
ArrayList<String> words = new ArrayList<>();

public void insertIntoTrie(ArrayList<String> newWords) {

    int n = newWords.size();
    for (int i = 0; i < n; i++) {
        insert(newWords.get(i));
    }}


public void getWordsList(TrieNode curNode,
                         String prefix) {

    if (curNode != null) {

        if (curNode.isLast)
            words.add(prefix);

        for (char i = 'a'; i <= 'z'; i++) {
            TrieNode nextNode = curNode.child.get(i);
            if (nextNode != null) {
                getWordsList(nextNode, prefix + i);
            }}}}


public void getShortest(String str) {
    TrieNode prevNode = root;
    TrieNode found = null;

    String prefix = "";
    int len = str.length();

    for (int i = 0; i < len; i++) {

        prefix += str.charAt(i);

        char lastChar = prefix.charAt(i);

        TrieNode curNode = prevNode.child.get(lastChar);
        found = curNode;

        if (curNode == null) {
            System.out.println("No Results Found!");
            i++;
            break;}
    prevNode = curNode; }

    getWordsList(found, prefix);

    if (words.size() != 0) {

        String shortestWord = words.get(0);

        for (int j = 1; j < words.size(); j++) {
            String nextWord = words.get(j);
            if (nextWord.compareTo(shortestWord) < 0) {
                shortestWord = nextWord;

            }}

        System.out.println("The shortest word is: " + shortestWord);
    }}}

Upvotes: 0

Views: 906

Answers (1)

Ori Cohen
Ori Cohen

Reputation: 185

Unless you need to save all the relevant words, there is no real reason to save them in a HashMap. Moreover, a HashMap is practically useless for iteration, since you need to access every word anyway. For your specific problem I would suggest to use a simple min search, i.e. search for the prefix and each time you run across it save it only if it's shorter that the word you currently have stored.

Upvotes: 0

Related Questions