CODEWITHSUNDEEP
java
Teddy13
Teddy13

Reputation: 3854

Print Tree components

I am new to java and I want to create a very simple "word completion " program. I will be reading in a dictionary file and recursively adding the words into a Node array (size 26). I believe I have managed to do this successfully but I am not sure how to go through and print the matches. For the sake of testing, I am simply inserting 2 words at the moment by calling the function. Once everything is working, I will add the method to read the file in and remove junk from the word.

For example: If the words "test" and "tester" are inside the tree and the user enters "tes", it should display "test" and "tester".

If somebody could please tell me how to go through and print the matches (if any), I would really appreciate it. Full code is below.

Thank you

Upvotes: 4

Views: 217

Answers (2)

khachik
khachik

Reputation: 28693

What you implemented is called "trie". You might want to look at the existing implementations.

What you used to store child nodes is called a hash table and you might want to use a standard implementations and avoid implementing it yourself unless you have very-very specific reasons to do that. Your implementation has some limitations (character range, for example).

I think, your code has a bug in method has:

...
else if (letter[val].flag==true || word.length()==1) {
    return true;
}

If that method is intended to return true if there are strings starting with word then it shouldn't check flag. If it must return true if there is an exact match only, it shouldn't check word.length().

And, finally, addressing your question: not the optimal, but the simplest solution would be to make a method, which takes a string and returns a node matching that string and a method that composes all the words from a node. Something like this (not tested):

class Tree {

    ...
    public List<String> matches(CharSequence prefix) {
        List<String> result = new ArrayList<>();
        if(r != null) {
            Node n = r._match(prefix, 0);
            if(n != null) {
                StringBuilder p = new StringBuilder();
                p.append(prefix);
                n._addWords(p, result);
            }
        }
        return result;
    }
}

class Node {

    ...
    protected Node _match(CharSequence prefix, int index) {
        assert index <= prefix.length();
        if(index == prefix.length()) {
            return this;
        }
        int val = prefix.charAt(index) - 'a';
        assert val >= 0 && val < letter.length;
        if (letter[val] != null) {
            return letter[val].match(prefix, index+1);
        }
        return null;
    }

    protected void _addWords(StringBuilder prefix, List<String> result) {
        if(this.flag) {
            result.add(prefix.toString());
        }    
        for(int i = 0; i<letter.length; i++) {
            if(letter[i] != null) {
                prefix.append((char)(i + 'a'));
                letter[i]._addWords(prefix, result);
                prefix.delete(prefix.length() - 1, prefix.length());
            }
        }
    }
}

Upvotes: 3

bogofh
bogofh

Reputation: 19

Maybe a longshot here, but why don't you try regexes here? As far as i understand you want to match words to a list of words:

List<String> getMatches(List<String> list, String regex) {

  Pattern p = Pattern.compile(regex);
  ArrayList<String> matches = new ArrayList<String>();

  for (String s:list) {
    if (p.matcher(s).matches()) {
      matches.add(s);
    }
  }

  return matches
}

Upvotes: -1

Related Questions