Trie

Partial search using Trie

Pinterest LinkedIn Tumblr

Write a program to display partial search in the hash map. When the user type S, the string start with S display. Example Eclipse or Visual studio editor displays the list of methods from object

Algorithm Explanation

The partial search is an auto complete future. It implemented using Trie.
Root node contains the alphabets.
Search operation searches the string.
If the match is null, it print no match found string. Otherwise, print the match string.

Source Code

package com.dsacode.DataStructre.trie;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
 
class TrieNodePartialSearch {
     
    public char character;
    private List < TrieNodePartialSearch > childs;
     
    public TrieNodePartialSearch(char charecter) {
        this.character = charecter;
        this.childs = new LinkedList < TrieNodePartialSearch > ();
    }
     
    public List < TrieNodePartialSearch >  getChilds() {
        return childs;
    }
    public void setChilds(List < TrieNodePartialSearch >  childs) {
        this.childs = childs;
    }
     
}
 
 
public class PartialSearchTrie {
     
    private TrieNodePartialSearch root;
 
    public void addWord(String word)
    {
        if(root == null)
        {
            root = new TrieNodePartialSearch(' ');
        }
        TrieNodePartialSearch start = root;
        char[] charecters = word.toCharArray();
        for(char c : charecters)
        {
            if( start.getChilds().size() == 0)
            {
                TrieNodePartialSearch newNode = new TrieNodePartialSearch(c);
                start.getChilds().add(newNode);
                start = newNode;
            }
            else
            {
                ListIterator < TrieNodePartialSearch > iterator = start.getChilds().listIterator();
                TrieNodePartialSearch node=null;
                while(iterator.hasNext())
                {
                    node = iterator.next();
                    if(node.character >= c)
                        break;
                }
                if(node.character == c)
                {
                    start = node;
                }
                else
                {
                    TrieNodePartialSearch newNode = new TrieNodePartialSearch(c);
                    iterator.add(newNode); 
                    start = newNode;
                     
                }
            }
        }
         
    }
     
     
    public List < String > search(String prefix){
        if(prefix == null || prefix.isEmpty())
            return null;
         
        char[] chars = prefix.toCharArray();
        TrieNodePartialSearch start = root;
        boolean flag = false;
        for(char c : chars) {
            if(start.getChilds().size() > 0){
                for(TrieNodePartialSearch node : start.getChilds()) {
                    if(node.character == c){
                        start = node;
                        flag=true;
                        break;
                    }
                }
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            List < String > matches = getAllWords(start,prefix);
            return matches;
        }
         
        return null;
    }
     
 
    private List < String > getAllWords(TrieNodePartialSearch start,final String prefix){
        if(start.getChilds().size() == 0){
            List < String > list = new LinkedList < String >();
            list.add(prefix);
            return list;
        }else{
            List < String > list = new LinkedList < String >();
            for(TrieNodePartialSearch n: start.getChilds()){
                list.addAll(getAllWords(n, prefix+n.character));
            }
            return list;
        }
    }
     
    public static void main(String[] args) {
        PartialSearchTrie trie = new PartialSearchTrie();
        String []array={"Hello","HelloWorld","HelloSiva","Hellostar","world","WorldHello"};
        for(String str: array)
            trie.addWord(str);
 
        System.out.println("All the words from Trie: " + Arrays.toString(array));
         
        System.out.println("Words contain 'Hello' from the Trie:");
        List < String > matches = trie.search("Hello");
         
        if(matches==null || matches.size() == 0){
            System.out.println("No match found");
        }else{
            for(String str:matches){
                System.out.println(str);
            }
        }
    }
 
}

Output

All the words from Trie: [Hello, HelloWorld, HelloSiva, Hellostar, world, WorldHello]
Words contain 'Hello' from the Trie:
HelloWorld
HelloSiva
Hellostar

Write A Comment