trie.java

import java.util.*;
import java.util.stream.*;

class Trie {
	public char nodeChar;
	public boolean isLeaf;
	public List<String> safeNames;
	public HashMap<Character, Trie> subtrie;
	
	Trie(char nodeChar, boolean isLeaf) {
		subtrie = new HashMap();
		safeNames = new ArrayList<>();
		this.nodeChar = nodeChar;
		this.isLeaf = isLeaf;
	}
	
	String compress(String word) {
		return word.toLowerCase().replace(" ", "");
	}
	
	public void insert(String word) {
		
		String trieWord = compress(word);		
		
		int len = trieWord.length();
		
		Trie parentTrie = this;
		
		for(int i = 0; i < len; i++) {
			char currentChar = trieWord.charAt(i);
			
			Trie currentTrie = parentTrie.subtrie.getOrDefault(currentChar, new Trie(currentChar, false));
			currentTrie.safeNames.add(word);
			currentTrie.isLeaf = (i + 1 == len);
			
			parentTrie.subtrie.put(currentChar, currentTrie);
			parentTrie = currentTrie;
		}
	}
	
	public void printTrie() {
		if (this.isLeaf) {
			System.out.println(this.safeNames.toString());
			return;
		}
		
		for (Trie tmp: this.subtrie.values()) 
			tmp.printTrie();
	}
	
	public void autocomplete(String prefix) {
		Trie tmp = this;
		
		for (int i = 0; i < prefix.length(); i++) {
			tmp = tmp.subtrie.get(prefix.charAt(i));
			if (tmp == null)
				return;
		}

		tmp.printTrie();
	}
	
	void checkDeepPaths(List<Trie> possiblePaths, char toBeFound) {
		if (this.isLeaf)
			return;
		
		for (Trie subtrie: this.subtrie.values()) 
			if (subtrie.nodeChar != toBeFound )
				subtrie.checkDeepPaths(possiblePaths, toBeFound);
			else
				possiblePaths.add(subtrie);
	}
	
	public void searchSubsequence(String sequence) {

		ArrayList<Trie> possiblePaths = new ArrayList<>(),
			searchablePaths = new ArrayList<>();
		
		searchablePaths.add(this);

		for (int i = 0; i < sequence.length(); i++) {
			for (Trie searchablePath : searchablePaths) 
				searchablePath.checkDeepPaths(possiblePaths, sequence.charAt(i));

			searchablePaths = (ArrayList<Trie>) possiblePaths.clone();
			possiblePaths.clear();
		}

		List<String> finalList = searchablePaths.stream()
			.map(p -> p.safeNames)
			.flatMap(Collection::stream)
			.collect(Collectors.toList());
			
		System.out.println(finalList);
			
	}
}

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Trie test = new Trie('\0', false);
		
		test.insert("Massachusetts Institute of Technology");
		test.insert("Madras institute of technology");
		test.insert("Madras Univ");
		test.insert("AMITY University");
		
		//test.autocomplete("mi");
		test.searchSubsequence("mit");
	}
}