fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Set;
  4.  
  5. class Dictionary {
  6.  
  7.  
  8. 	public static void main(String[] args) {
  9. 		ArrayList<String> dictionary = new ArrayList<String>();
  10. 		dictionary.add("abc");
  11. 		dictionary.add("acd");
  12. 		dictionary.add("bcc");
  13. 		dictionary.add("bed");
  14. 		dictionary.add("bdc");
  15. 		dictionary.add("dab");
  16.  
  17. 		ArrayList<CharNode> treeList = new ArrayList<CharNode>() ;
  18. 		buildDictionaryTree(dictionary,treeList);
  19. 		System.out.println("Printing trees");
  20. 		for(CharNode lst:treeList){
  21. 			System.out.println(lst);
  22. 		}
  23.  
  24. 		reconcileTrees(treeList);
  25.  
  26.  
  27. 		System.out.println("Final tree is ");
  28. 		System.out.println(treeList.get(0));
  29. 		System.out.println("done");
  30.  
  31. 	}
  32.  
  33. 	public static void reconcileTrees(ArrayList<CharNode> treeList){
  34. 		while(treeList.size()>1){
  35. 			for(int i =0;i<treeList.size();i++){
  36. 				for(int j =i+1;j<treeList.size();j++){
  37. 					 mergeOrModifyTwoTrees(treeList,i,j,true);
  38. 					 // if list is not modified call reverse way
  39. 					 if(i<treeList.size() && j<treeList.size()){
  40. 						 mergeOrModifyTwoTrees(treeList,j,i,true);
  41. 					 }
  42. 				}
  43. 			}
  44. 		}
  45. 	}
  46.  
  47. 	public static void mergeOrModifyTwoTrees(ArrayList<CharNode> treeList , int first , int secodnd,boolean firstCall){
  48. 		CharNode t1 = treeList.get(first);
  49. 		CharNode t2 = treeList.get(secodnd);
  50. 		// Check if root of t2 is found in tree of t1
  51. 		CharNode currOfT1 = t1;
  52. 		CharNode currOfT2 = t2;
  53. 		CharNode lastMatchingNodeOfT1 =null,lastMatchingNodeOfT2=null;
  54. 		while(currOfT2!=null){
  55. 			while(currOfT1 != null && currOfT1.value !=currOfT2.value ){
  56. 				currOfT1 = currOfT1.nextNode;
  57. 			}
  58. 			if(currOfT1 != null){   
  59. 				// loop ended when currOfT1 so match for t2 found in t1 
  60. 				// So go for next of t2
  61. 				lastMatchingNodeOfT1 = currOfT1;
  62. 				lastMatchingNodeOfT2 = currOfT2;
  63. 				currOfT2 = currOfT2.nextNode;
  64. 			}else{
  65. 				// no match found for current node
  66. 				break;
  67. 			}
  68. 		}
  69. 		if(lastMatchingNodeOfT1 == null && lastMatchingNodeOfT2 == null){
  70. 			return;
  71. 		}
  72. 		if(currOfT2==null){
  73. 			// t2 is completely present in t1 directly or indirectly
  74. 			// So remove from arrayList
  75. 			treeList.remove(t2);
  76. 		}else{
  77. 			// There is part of t2 that is not present in t1
  78. 			if(lastMatchingNodeOfT1 != null && lastMatchingNodeOfT1.nextNode ==null){
  79. 				// lastMatchingNodeOfT1 was a leaf node then you can append remaining of t2 there
  80. 				lastMatchingNodeOfT1.nextNode = currOfT2;
  81. 				treeList.remove(t2);
  82. 			}else{
  83. 				// lastMatchingNodeOfT1 is not present or NOT leaf.
  84. 				// Do reverse way. Check if next of lastMatchingNodeOfT1 is present t2
  85. 				// e.g. t1==a->b->d   t2 == b->c->e->d
  86. 				// lastMatchingNodeOfT1 == b->d
  87. 				// lastMatchingNodeOfT2 == b->c->e->d
  88. 				// So check if lastMatchingNodeOfT1.nextNode i.e. "d" is present in  lastMatchingNodeOfT2
  89. 				CharNode temp = lastMatchingNodeOfT2.nextNode;
  90. 				CharNode nodeBeforeTemp = lastMatchingNodeOfT2;
  91. 				while(temp !=null && temp.value != lastMatchingNodeOfT1.nextNode.value){
  92. 					nodeBeforeTemp = temp;
  93. 					temp = temp.nextNode;
  94. 				}
  95. 				// t1== a->b->d->n  t2 == b->c->e->d->m
  96. 				// them lastMatchingNodeOfT1=lastMatchingNodeOfT2= b
  97. 				// lastMatchingNodeOfT1.next = d->n
  98. 				// temp = d->m
  99. 				// nodeBeforeTemp = e->d->m
  100. 				// 
  101. 				if(temp !=null ){
  102. 					nodeBeforeTemp.nextNode = lastMatchingNodeOfT1.nextNode;  //   e->d->n
  103. 					lastMatchingNodeOfT1.nextNode = lastMatchingNodeOfT2.nextNode;  // a->b->c
  104. 					// together it became a->b->c->e->d->n
  105.  
  106. 					if(temp.nextNode !=null){
  107. 						treeList.remove(t2);
  108. 						treeList.add(secodnd, temp);   // d->m added as separate string
  109. 					}else{
  110. 						// t2 is completely consumed
  111. 						treeList.remove(t2);
  112. 					}
  113. 				}
  114.  
  115. 			}
  116. 		}
  117.  
  118. 		// do the same for reverse
  119.  
  120. 	}
  121.  
  122.  
  123.  
  124. 	public static void buildDictionaryTree(ArrayList<String> dictionary, ArrayList<CharNode> treeList){
  125. 	//System.out.println("Input strings are");
  126. 	//System.out.println(dictionary);
  127. 	if(dictionary.size()>1){
  128. 		CharNode currentNode = null;
  129. 		HashMap<Character, ArrayList<String>> charStringMap = new HashMap<Character, ArrayList<String>>();
  130. 		for(String str : dictionary){
  131. 			char firstChar = str.charAt(0);
  132. 			ArrayList<String> strlst = charStringMap.get(firstChar);
  133. 			if(strlst==null){
  134. 				//first time this character was visited
  135. 				strlst = new ArrayList<String>();
  136. 				charStringMap.put(firstChar,strlst);
  137. 			}
  138. 			// If this string is more than one character add substring to this list
  139. 			if(str.length()>1){
  140. 				strlst.add(str.substring(1));
  141. 			}
  142.  
  143. 			if(currentNode==null){
  144. 				// First time creating tree in this call. So create node and also add it in input tree list 
  145. 				currentNode = new CharNode(firstChar);
  146. 				treeList.add(currentNode);
  147. 			}else{
  148. 				if(currentNode.value==firstChar){
  149. 					// We are still processing strings starting with same character so no need to add in tree
  150. 				}else{
  151. 					currentNode.nextNode=new CharNode(firstChar);
  152. 					currentNode= currentNode.nextNode;
  153. 				}
  154. 			}
  155. 		}
  156.  
  157. 		// All first character done. Now call same process for substrings one by one
  158. 		// Each call will create a separate tree
  159. 		Set<Character> charCovered =  charStringMap.keySet();
  160. 		for(char ch:charCovered){
  161. 			buildDictionaryTree(charStringMap.get(ch),treeList);
  162. 		}
  163. 	}else{
  164. 		//System.out.println("Only one string. No use");
  165. 	}
  166.  
  167. }
  168. }
  169. class CharNode{
  170. 	char value;
  171. 	CharNode nextNode;
  172.  
  173. 	public CharNode(char value) {
  174. 		this.value=value;
  175. 	}
  176.  
  177. 	@Override
  178. 	public String toString() {
  179. 		if(nextNode!=null){
  180. 			return value+"->"+nextNode.toString();
  181. 		}else{
  182. 			return value+"";
  183. 		}
  184.  
  185. 	}
  186.  
  187. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Printing trees
a->b->d
c->e->d
b->c
Final tree is 
a->b->c->e->d
done
https://ideone.com/W7NMpN
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!