HelpMePradyumana.java

/*Help Me Pradyumana!
Send Feedback
Pradyumn is tired of using auto - correct feature in his smartphone. He needs to correct his auto - correct more times than the auto - correct corrects him. Pradyumn is thinking to make his own app for mobile which will restrict auto - correct feature, instead it will provide auto - completion. Whenever Pradyumn types factorial, auto - correct changes it to fact. Pradyumn's App will show options such as fact, factorial, factory. Now, he can chose from any of these options. As Pradyumn is busy with his front - end work of his App. He asks you to help him. He said "You will be given set of words(words may repeat too but counted as one only). Now, as user starts the app, he will make queries(in lowercase letters only). So, you have to print all the words of dictionary which have the prefix same as given by user as input. And if no such words are available, add this word to your dictionary." As you know, Pradyumn want this app to be as smart as him :P So, implement a program for him such that he can release it on Fun Store.
INPUT CONSTRAINTS
1≤N≤30000
sum(len(string[i]))≤2∗10^5
1≤Q≤10^3
INPUT FORMAT
Single integer N which denotes the size of words which are input as dictionary
N lines of input, where each line is a string of consisting lowercase letter
Single integer Q which denotes the number of queries.
Q number of lines describing the query string on each line given by user
OUTPUT FORMAT
If auto - completions exists, output all of them in lexicographical order else output "No suggestions" without quotes

NOTE: All strings are lowercase
SAMPLE INPUT
3
fact
factorial
factory
2
fact
pradyumn
SAMPLE OUTPUT
fact
factorial
factory
No suggestions*/

import java.util.*;
class TrieNode{
	TrieNode children[] = new TrieNode[26];
    Set<String> l = new HashSet<>();
    TrieNode(Set<String> l){
		this.l = l;
    }
}
public class HelpMePradyumana {
   public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TrieNode head = new TrieNode(new HashSet<>());
        for(int i=0;i<n;i++){ insert(head,sc.next()); }
		int q = sc.nextInt();
        for(int i=0;i<q;i++){
        String s = sc.next();
            //flag = false;
        TrieNode node = query(head,s);
        if(node == null){
            System.out.println("No suggestions");
			insert(head,s);   
        }else { TreeSet<String> set = new TreeSet<>(node.l); set.stream().forEach(str->
                        System.out.println(str)); }
        }
	}

    static void insert(TrieNode head, String s){
		TrieNode cur = head;
        for(int i=0;i<s.length();i++){
            int x = s.charAt(i) - 'a';
			if(cur.children[x] == null){
				cur.children[x] = new TrieNode(new HashSet<>());
            }
            cur.children[x].l.add(s);
            cur = cur.children[x];
        }
    }
    
    static TrieNode query(TrieNode head, String s){
		TrieNode cur = head;
        TrieNode ans = null;
        for(int i=0;i<s.length();i++){
           // System.out.println(s.charAt(i));
			int x =s.charAt(i) - 'a';
            if(cur.children[x] == null){
				//cur.children[x] = new TrieNode(new ArrayList<>());
               //cur.children[x];
                    break;
            }
            cur = cur.children[x];
            if(i == s.length()-1){ ans = cur;}
        }
        return ans;
    }
}