Trie

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
// trie using HashMap - o(n)
class TrieHashMap {
boolean isExits;
Map<Character, TrieHashMap> hm;

TrieHashMap() {
this.isExits = false;
hm = new HashMap();
}

public void insertUsingHashMap(String key) {
TrieHashMap temp = this;
for (int i = 0; i < key.length(); i++) {
if (temp.hm.get(key.charAt(i)) == null) {
temp.hm.put(key.charAt(i), new TrieHashMap());
}
temp = temp.hm.get(key.charAt(i));
}
}

public void dictSearch(TrieHashMap root, String key) {
TrieHashMap temp = root;
int counter = 0;
int i = 0;
while (i < key.length() - 1) {
if (temp.hm.get(key.charAt(i)) != null) {
temp = temp.hm.get(key.charAt(i));
i++;
} else {
counter++;
temp = root;
}
}
System.out.println("ans" + counter);
}
}

class TrieList {
private static final int CHAR_SIZE = 26;
boolean isExists;
List<TrieList> li;

public TrieList() {
isExists = false;
li = new ArrayList<>();
for (int i = 0; i < CHAR_SIZE; i++) {
li.add(null);
}

}

public void insert(String key) {
System.out.println("inserting " + key);
TrieList temp = this;
for (int i = 0; i < key.length(); i++) {
if (temp.li.get(key.charAt(i) - 'a') == null) {
temp.li.set(key.charAt(i) - 'a', new TrieList());
}
temp = temp.li.get(key.charAt(i) - 'a');
}
temp.isExists = true;
}

public boolean singleWordSearch(TrieList root, String key) {
TrieList temp = root;
for (int i = 0; i < key.length(); i++) {
temp = temp.li.get(key.charAt(i) - 'a');
if (temp == null) {
return false;
}
}
return temp.isExists;
}

public void dictSearch(TrieList root, String key) {
TrieList temp = root;
int counter = 0;
int i = 0;
while (i < key.length() - 1) {
if (temp.li.get(key.charAt(i) - 'a') != null) {
temp = temp.li.get(key.charAt(i) - 'a');
i++;
} else {
counter++;
temp = root;
}
}
System.out.println("ans" + counter);
}
}

public class wordBreakTrieList {

public static void main(String[] args) {
// TODO Auto-generated method stub
TrieList t = new TrieList();
t.insert("java");
t.insert("java progr");
t.insert("jaa");
System.out.println("inserted");
String[] dictionary = { "i", "like", "face", "book", "facebook" };
String input = "ilikefacebook";
for (String s : dictionary) {
t.insert(s);
// root.addString(s);
}
System.out.println(t.singleWordSearch(t, "java"));
t.dictSearch(t, input);
TrieHashMap ht = new TrieHashMap();
for (String s : dictionary) {
ht.insertUsingHashMap(s);
}
ht.dictSearch(ht, input);

}

}