import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

class Dictionary {

	
	public static void main(String[] args) {
		ArrayList<String> dictionary = new ArrayList<String>();
		dictionary.add("abc");
		dictionary.add("acd");
		dictionary.add("bcc");
		dictionary.add("bed");
		dictionary.add("bdc");
		dictionary.add("dab");
		
		ArrayList<CharNode> treeList = new ArrayList<CharNode>() ;
		buildDictionaryTree(dictionary,treeList);
		System.out.println("Printing trees");
		for(CharNode lst:treeList){
			System.out.println(lst);
		}
		
		reconcileTrees(treeList);
		
		
		System.out.println("Final tree is ");
		System.out.println(treeList.get(0));
		System.out.println("done");
		
	}
	
	public static void reconcileTrees(ArrayList<CharNode> treeList){
		while(treeList.size()>1){
			for(int i =0;i<treeList.size();i++){
				for(int j =i+1;j<treeList.size();j++){
					 mergeOrModifyTwoTrees(treeList,i,j,true);
					 // if list is not modified call reverse way
					 if(i<treeList.size() && j<treeList.size()){
						 mergeOrModifyTwoTrees(treeList,j,i,true);
					 }
				}
			}
		}
	}
	
	public static void mergeOrModifyTwoTrees(ArrayList<CharNode> treeList , int first , int secodnd,boolean firstCall){
		CharNode t1 = treeList.get(first);
		CharNode t2 = treeList.get(secodnd);
		// Check if root of t2 is found in tree of t1
		CharNode currOfT1 = t1;
		CharNode currOfT2 = t2;
		CharNode lastMatchingNodeOfT1 =null,lastMatchingNodeOfT2=null;
		while(currOfT2!=null){
			while(currOfT1 != null && currOfT1.value !=currOfT2.value ){
				currOfT1 = currOfT1.nextNode;
			}
			if(currOfT1 != null){   
				// loop ended when currOfT1 so match for t2 found in t1 
				// So go for next of t2
				lastMatchingNodeOfT1 = currOfT1;
				lastMatchingNodeOfT2 = currOfT2;
				currOfT2 = currOfT2.nextNode;
			}else{
				// no match found for current node
				break;
			}
		}
		if(lastMatchingNodeOfT1 == null && lastMatchingNodeOfT2 == null){
			return;
		}
		if(currOfT2==null){
			// t2 is completely present in t1 directly or indirectly
			// So remove from arrayList
			treeList.remove(t2);
		}else{
			// There is part of t2 that is not present in t1
			if(lastMatchingNodeOfT1 != null && lastMatchingNodeOfT1.nextNode ==null){
				// lastMatchingNodeOfT1 was a leaf node then you can append remaining of t2 there
				lastMatchingNodeOfT1.nextNode = currOfT2;
				treeList.remove(t2);
			}else{
				// lastMatchingNodeOfT1 is not present or NOT leaf.
				// Do reverse way. Check if next of lastMatchingNodeOfT1 is present t2
				// e.g. t1==a->b->d   t2 == b->c->e->d
				// lastMatchingNodeOfT1 == b->d
				// lastMatchingNodeOfT2 == b->c->e->d
				// So check if lastMatchingNodeOfT1.nextNode i.e. "d" is present in  lastMatchingNodeOfT2
				CharNode temp = lastMatchingNodeOfT2.nextNode;
				CharNode nodeBeforeTemp = lastMatchingNodeOfT2;
				while(temp !=null && temp.value != lastMatchingNodeOfT1.nextNode.value){
					nodeBeforeTemp = temp;
					temp = temp.nextNode;
				}
				// t1== a->b->d->n  t2 == b->c->e->d->m
				// them lastMatchingNodeOfT1=lastMatchingNodeOfT2= b
				// lastMatchingNodeOfT1.next = d->n
				// temp = d->m
				// nodeBeforeTemp = e->d->m
				// 
				if(temp !=null ){
					nodeBeforeTemp.nextNode = lastMatchingNodeOfT1.nextNode;  //   e->d->n
					lastMatchingNodeOfT1.nextNode = lastMatchingNodeOfT2.nextNode;  // a->b->c
					// together it became a->b->c->e->d->n
					
					if(temp.nextNode !=null){
						treeList.remove(t2);
						treeList.add(secodnd, temp);   // d->m added as separate string
					}else{
						// t2 is completely consumed
						treeList.remove(t2);
					}
				}

			}
		}
		
		// do the same for reverse
		
	}
		

	
	public static void buildDictionaryTree(ArrayList<String> dictionary, ArrayList<CharNode> treeList){
	//System.out.println("Input strings are");
	//System.out.println(dictionary);
	if(dictionary.size()>1){
		CharNode currentNode = null;
		HashMap<Character, ArrayList<String>> charStringMap = new HashMap<Character, ArrayList<String>>();
		for(String str : dictionary){
			char firstChar = str.charAt(0);
			ArrayList<String> strlst = charStringMap.get(firstChar);
			if(strlst==null){
				//first time this character was visited
				strlst = new ArrayList<String>();
				charStringMap.put(firstChar,strlst);
			}
			// If this string is more than one character add substring to this list
			if(str.length()>1){
				strlst.add(str.substring(1));
			}
			
			if(currentNode==null){
				// First time creating tree in this call. So create node and also add it in input tree list 
				currentNode = new CharNode(firstChar);
				treeList.add(currentNode);
			}else{
				if(currentNode.value==firstChar){
					// We are still processing strings starting with same character so no need to add in tree
				}else{
					currentNode.nextNode=new CharNode(firstChar);
					currentNode= currentNode.nextNode;
				}
			}
		}
		
		// All first character done. Now call same process for substrings one by one
		// Each call will create a separate tree
		Set<Character> charCovered =  charStringMap.keySet();
		for(char ch:charCovered){
			buildDictionaryTree(charStringMap.get(ch),treeList);
		}
	}else{
		//System.out.println("Only one string. No use");
	}

}
}
class CharNode{
	char value;
	CharNode nextNode;
	
	public CharNode(char value) {
		this.value=value;
	}
	
	@Override
	public String toString() {
		if(nextNode!=null){
			return value+"->"+nextNode.toString();
		}else{
			return value+"";
		}
		
	}
	
}