import java.util.HashMap;
public class TrieNode
{
private char character;
private HashMap<Character, TrieNode> children;
private boolean isEnd;
TrieNode(char character)
{
this.character = character;
children = new HashMap<>();
isEnd = false;
}
public char getCharacter()
{
return character;
}
public void setCharacter(char character)
{
this.character = character;
}
public HashMap<Character, TrieNode> getChildren()
{
return children;
}
public void setChildren(HashMap<Character, TrieNode> children)
{
this.children = children;
}
public boolean isEnd()
{
return isEnd;
}
public void setEnd(boolean isEnd)
{
this.isEnd = isEnd;
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map.Entry;
public class TrieOperations
{
private TrieNode root;
private static int totalFoundWords;
public TrieOperations()
{
root = new TrieNode((char)0);
totalFoundWords =0;
}
public void insert(String word)
{
int length = word.length();
TrieNode temp = root;
for (int i = 0; i < length; i++)
{
char ch = word.charAt(i);
HashMap<Character, TrieNode> child = temp.getChildren();
if (child.containsKey(ch))
{
temp = child.get(ch);
}
else
{
TrieNode next = new TrieNode(ch);
child.put(ch, next);
temp = next;
}
}
temp.setEnd(true);
}
public void patterMatching(String word)
{
int length = word.length();
TrieNode temp = root;
String value = "";
boolean cont = false;
for (int i = 0; i < length; i++)
{
char ch = word.charAt(i);
HashMap<Character, TrieNode> child = temp.getChildren();
if (child.containsKey(ch))
{
temp = child.get(ch);
cont = true;
value += ch;
}
else
{
cont = false;
break;
}
}
if (cont)
{
findPossibleStrings(value, temp);
}
System.out.println(totalFoundWords +" words are found");
}
private void findPossibleStrings(String value, TrieNode temp)
{
if (temp.isEnd())
{
System.out.println(value);
totalFoundWords++;
}
HashMap<Character, TrieNode> child = temp.getChildren();
for (Entry<Character, TrieNode> entry : child.entrySet())
{
value += entry.getKey();
findPossibleStrings(value, entry.getValue());
value = value.substring(0, value.length() - 1);
}
}
public static void main(String[] args)
{
TrieOperations opr = new TrieOperations();
//you can get the list of words from https://raw.githubusercontent.com/dwyl/english-words/master/words.txt
File file = new File(Your list of words file);
BufferedReader br = null;
try
{
br = new BufferedReader(new FileReader(file));
String line;
while ((line = br.readLine()) != null)
{
opr.insert(line.trim());
}
}
catch (IOException e)
{
e.printStackTrace();
}
finally
{
if (null != br)
{
try
{
br.close();
}
catch (IOException e)
{
e.printStackTrace();
}
}
}
String input = "prabhu";
opr.patterMatching(input);
}
}
public class TrieNode
{
private char character;
private HashMap<Character, TrieNode> children;
private boolean isEnd;
TrieNode(char character)
{
this.character = character;
children = new HashMap<>();
isEnd = false;
}
public char getCharacter()
{
return character;
}
public void setCharacter(char character)
{
this.character = character;
}
public HashMap<Character, TrieNode> getChildren()
{
return children;
}
public void setChildren(HashMap<Character, TrieNode> children)
{
this.children = children;
}
public boolean isEnd()
{
return isEnd;
}
public void setEnd(boolean isEnd)
{
this.isEnd = isEnd;
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map.Entry;
public class TrieOperations
{
private TrieNode root;
private static int totalFoundWords;
public TrieOperations()
{
root = new TrieNode((char)0);
totalFoundWords =0;
}
public void insert(String word)
{
int length = word.length();
TrieNode temp = root;
for (int i = 0; i < length; i++)
{
char ch = word.charAt(i);
HashMap<Character, TrieNode> child = temp.getChildren();
if (child.containsKey(ch))
{
temp = child.get(ch);
}
else
{
TrieNode next = new TrieNode(ch);
child.put(ch, next);
temp = next;
}
}
temp.setEnd(true);
}
public void patterMatching(String word)
{
int length = word.length();
TrieNode temp = root;
String value = "";
boolean cont = false;
for (int i = 0; i < length; i++)
{
char ch = word.charAt(i);
HashMap<Character, TrieNode> child = temp.getChildren();
if (child.containsKey(ch))
{
temp = child.get(ch);
cont = true;
value += ch;
}
else
{
cont = false;
break;
}
}
if (cont)
{
findPossibleStrings(value, temp);
}
System.out.println(totalFoundWords +" words are found");
}
private void findPossibleStrings(String value, TrieNode temp)
{
if (temp.isEnd())
{
System.out.println(value);
totalFoundWords++;
}
HashMap<Character, TrieNode> child = temp.getChildren();
for (Entry<Character, TrieNode> entry : child.entrySet())
{
value += entry.getKey();
findPossibleStrings(value, entry.getValue());
value = value.substring(0, value.length() - 1);
}
}
public static void main(String[] args)
{
TrieOperations opr = new TrieOperations();
//you can get the list of words from https://raw.githubusercontent.com/dwyl/english-words/master/words.txt
File file = new File(Your list of words file);
BufferedReader br = null;
try
{
br = new BufferedReader(new FileReader(file));
String line;
while ((line = br.readLine()) != null)
{
opr.insert(line.trim());
}
}
catch (IOException e)
{
e.printStackTrace();
}
finally
{
if (null != br)
{
try
{
br.close();
}
catch (IOException e)
{
e.printStackTrace();
}
}
}
String input = "prabhu";
opr.patterMatching(input);
}
}