/*
 * Author: Ruo Ding
 * Date: June 26, 2012
 */
import java.io.File;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;


public class SimpleTrie {

	/**
	 * @param args
	 */
	private SimpleTrieNode root;
	private SimpleTrieNode head;
	public SimpleTrie()
	{
		root = new SimpleTrieNode();
		head = null;
	}
	
	public void initTrie(String aWord)
	{
		if (head!=null)
			return;
		
		SimpleTrieNode scanningNode = root;
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			String subWord = aWord.substring(0, i+1);
			scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
			scanningNode = scanningNode.subNodes[iChar];
		}
		scanningNode.isWord = true;
		head = scanningNode;
	}
	
	public void insert(String word)
	{
		SimpleTrieNode scanningNode = root;
		String aWord = word.toLowerCase();
		
		if (head == null)
		{
			initTrie(aWord);
			return;
		}
		
		SimpleTrieNode nextWord = null;
		SimpleTrieNode prevWord = null;
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (scanningNode.subNodes[iChar] != null)
			{
				scanningNode = scanningNode.subNodes[iChar];
				
				if (scanningNode.values.length == aWord.length() &&
					scanningNode.toString().equals(aWord) &&
					!scanningNode.isWord)
				{
					// if the word occur as a prefix in our list, 
					// than find the fist word with this prefix, insert this in the front
					nextWord = findNextWord(scanningNode, 0);
					scanningNode.isWord = true;
					if (nextWord.prev != null)
					{
						prevWord = nextWord.prev;
						prevWord.next = scanningNode;
						scanningNode.prev = prevWord;
					}
					
					scanningNode.next = nextWord;
					nextWord.prev = scanningNode;
					return;
				}
			}else
			{
				if (prevWord == null && nextWord == null)
				{
					nextWord = findNextWord(scanningNode, iChar+1);
					prevWord = findPrevWord(scanningNode, iChar-1);					
				}
				String subWord = aWord.substring(0, i+1);
				scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
				scanningNode = scanningNode.subNodes[iChar];
			}
		}
		scanningNode.isWord = true;
		
		if (prevWord != null)
		{
			prevWord.next = scanningNode;
			scanningNode.prev = prevWord;
		}
		if (nextWord != null)
		{
			nextWord.prev = scanningNode;
			scanningNode.next = nextWord;
		}
	}
	
	public SimpleTrieNode find(String word)
	{
		if (head == null)
		{
			return null;
		}
		
		
		SimpleTrieNode scanningNode = root;
		String aWord = word.toLowerCase();
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (scanningNode.subNodes[iChar] != null)
			{
				scanningNode = scanningNode.subNodes[iChar];
				if (scanningNode.values.length == aWord.length())
				{
					if (scanningNode.isWord)
					{
						return scanningNode;
					}else
					{
						return null;
					}
				}
			}else
			{
				return null;
			}	
		}
		
		return null;
	}
	
	public SimpleTrieNode remove(String word)
	{
		SimpleTrieNode toRemove = find(word);
		if(toRemove.prev!=null)
		{
			toRemove.prev.next = toRemove.next;
		}
		if(toRemove.next!=null)
		{
			toRemove.next.prev = toRemove.prev;
		}
		return toRemove;
	}
	
	
	public SimpleTrieNode getHead() {
		return head;
	}
	
	// give the parent node and the index starts to scan in parent node
	public SimpleTrieNode findNextWord(SimpleTrieNode node, int cIndex)
	{
		if (node == null)
			return null;
		
		String subWord = node.toString();
		
		for (int i = cIndex; i<node.subNodes.length; i++)
		{
			if (node.subNodes[i] != null)
			{
				if (node.subNodes[i].isWord)
				{
					return node.subNodes[i];
				}else
				{
					return findNextWord(node.subNodes[i], 0);
				}
			}
		}
		
		// none found in the same or below level, proceed to the next in its parent level
		SimpleTrieNode theParent = null;
		for (int i = 0; i < subWord.length()-1; i++)
		{
			if (theParent == null)
			{
				theParent = root;
			}
			char letter = subWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (theParent.subNodes[iChar]!=null)
			{
				theParent = theParent.subNodes[iChar];
			}else
			{
				return null;
			}
		}
		
		int nextIndex = -1;
		if (subWord.length()>=1)
		{
			char nextChar = subWord.charAt(subWord.length()-1);
			nextIndex = Character.getNumericValue(nextChar) - 10;
		}
		return findNextWord(theParent, nextIndex+1);
		
	}
	
	// give the parent node and the index starts to scan in parent node
	public SimpleTrieNode findPrevWord(SimpleTrieNode node, int cIndex)
	{
		if (node == null)
			return null;
		
		String subWord = node.toString();
		
		for (int i = cIndex; i >= 0; i--)
		{
			if (node.subNodes[i] != null)
			{
				SimpleTrieNode rSubNode = findPrevWord(node.subNodes[i], 25);
				if (rSubNode != null)
				{
					return rSubNode;
				}else if (node.subNodes[i].isWord)
				{
					return node.subNodes[i];
				}
			}
		}
		
		//if none exist before the index in the node child, check if node is a word 
		if (node.isWord)
		{
			return node;
		}
		
		// none found in the same or below level, proceed to the prev in its parent level
		SimpleTrieNode theParent = null;
		int iChar = -1;
		int i;
		for ( i = 0; i < subWord.length()-1; i++)
		{
			if (theParent == null)
			{
				theParent = root;
			}
			char letter = subWord.charAt(i);
			iChar = Character.getNumericValue(letter) - 10;
			if (theParent.subNodes[iChar]!=null)
			{
				theParent = theParent.subNodes[iChar];
			}else
			{
				return null;
			}
		}
		int nextIndex = -1;
		if (subWord.length()>=1)
		{
			char nextChar = subWord.charAt(subWord.length()-1);
			nextIndex = Character.getNumericValue(nextChar) - 10;
		}
		return findPrevWord(theParent, nextIndex-1);
		
	}
	
	
	// main just test some basic functions for this SimpleTrie
	public static void main(String[] args) {
		
		SimpleTrie ourTrie = new SimpleTrie();
		File dbFile = new File("dictionary.txt");
		int wordsCount = 0;
		int nodesCount = 0;
		ArrayList<String> allWords = new ArrayList<String>();
		Hashtable<String, Integer> table = new Hashtable<String, Integer>();
		int duplicateCounts = 0;
		try{
			
			if (dbFile.exists())
			{
				Scanner preProcessor = new Scanner(dbFile);
				while (preProcessor.hasNextLine())
				{
					
					String theWord = preProcessor.nextLine();
					if (theWord.equals("abalone"))
					{
						System.out.println("Hit abalone");
					}
					ourTrie.insert(theWord);
					allWords.add(theWord);
					wordsCount++;
					if (table.get(theWord)!=null)
					{
						duplicateCounts++;
					}
					table.put(theWord, new Integer(1));
				}
				preProcessor.close();
			}
			SimpleTrieNode aR = ourTrie.remove("zimbalon");
			System.out.println(aR.toString());
			SimpleTrieNode printNode = ourTrie.getHead();
			while(printNode!=null)
			{
				//System.out.println(printNode.toString());
				printNode = printNode.next;
				nodesCount++;
			}
			
			for (int i = 0; i< allWords.size(); i++)
			{
				String aWord = allWords.get(i);
				if (ourTrie.find(aWord) == null)
				{
					System.out.println("Word: \'" + aWord + "\' not found!");
				}
			}
			
			
		}catch(Exception e)
		{
			System.out.println("Faild with Error: " + e.getMessage() + ", at line: " + wordsCount + ", at node " + nodesCount);
		}
		
		
		
		System.out.println("TotalWord from dic is: " + wordsCount + ", and total nodes is: " + nodesCount + ", dupcount: " + duplicateCounts);

	}

}




public class SimpleTrieNode {

	/**
	 * @param args
	 */
	public SimpleTrieNode prev;
	public SimpleTrieNode next;
	public SimpleTrieNode[] subNodes;
	public char[] values;
	public char sValue;
	public boolean isWord; // true indicate the node contains a word in our dictionary
	
	public SimpleTrieNode()
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
	}
	
	public SimpleTrieNode(String word)
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
		values = word.toCharArray();
		if (values.length >= 1)
		{
			sValue = values[values.length-1];
		}
	}
	
	
	public String toString()
	{
		if (values == null)
			return "";
		
		return new String(values);
	}
}

/*
 * Author: Ruo Ding
 * Date: June 22, 2012
 */

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Scanner;


public class SmallDatabase {
	
	public static final String dbFileName = "SmallDatabaseRecords.txt";

	Hashtable<String, RecordNode> all_records = new Hashtable<String, RecordNode>();
	HashSet<Integer> all_values = new HashSet<Integer>();
	private boolean terminates;
	private CommandNode transactionCommandPointer;
	private ArrayList<RecordNode> transactionRecords;
	
	public static void main(String[] args) {
		File dbFile = new File(dbFileName);
		try{
			Hashtable<String, RecordNode> oldRecords = new Hashtable<String, RecordNode>();
			HashSet<Integer> valueSet = new HashSet<Integer>();
			if (dbFile.exists())
			{
				Scanner preProcessor = new Scanner(dbFile);
				while (preProcessor.hasNextLine())
				{
					RecordNode aRecord = makeRecord(preProcessor.nextLine());
					if (aRecord != null)
					{
						Integer trial_value = new Integer(aRecord.getValue());
						if (valueSet.contains(trial_value))
						{
							getFirstWithValue(oldRecords, trial_value).setNext(aRecord);
						}else
						{
							valueSet.add(new Integer(aRecord.getValue()));
						}
						oldRecords.put(aRecord.getName(), aRecord);
					}
				}
				preProcessor.close();
			}
			SmallDatabase mydb = new SmallDatabase(oldRecords, valueSet);
			
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String inputLine = null;
			while (!mydb.isTerminated())
			{
				inputLine = br.readLine();
				if (inputLine.equals("END"))
				{
					mydb.setTerminates(true);
					continue;
				}
				
				CommandNode aCommand = makeCommand(inputLine);
				if (aCommand != null)
				{
					mydb.processCommand(aCommand);
				}
			}
			if (dbFile.exists())
			{
				dbFile.delete();
			}
			dbFile.createNewFile();
			FileWriter fstream = new FileWriter(dbFile);
			BufferedWriter out = new BufferedWriter(fstream);
			Hashtable<String, RecordNode> finalRecords = mydb.getAll_records();
			Enumeration<String> e = finalRecords.keys();
			while (e.hasMoreElements())
			{
				String aKey = e.nextElement();
				RecordNode currentNode = finalRecords.get(aKey);
				out.write(aKey + " " + currentNode.getValue() + "\n");
			}
			out.close();
			
		}catch(Exception e)
		{
			System.out.println("Processing Database Records Faild with Error: " + e.getMessage());
		}
	}
	
	
	public SmallDatabase(Hashtable<String, RecordNode> table, HashSet<Integer> values)
	{
		all_records = table;
		all_values = values;
		terminates = false;
		transactionCommandPointer = null;
		transactionRecords = null;
	}
	
	public void processCommand(CommandNode aCommand) {
		
		switch (aCommand.getCommandId()) {
			case CommandNode.SET:
				dbSet(aCommand);
				break;
			case CommandNode.GET:
				dbGet(aCommand.getName());
				break;
			case CommandNode.UNSET:
				dbUnset(aCommand);
				break;
			case CommandNode.NUMEQUALTO:
				System.out.println(dbGetCount(aCommand.getValue()));
				break;
			case CommandNode.BEGIN:
				dbTranBegin(aCommand);
				break;
			case CommandNode.ROLLBACK:
				dbRollBack(aCommand);
				break;
			case CommandNode.COMMIT:
				dbCommit();
				break;
			default:
				break;
		}
		
	}
	
	private void dbCommit() {
		if (transactionCommandPointer == null || transactionRecords == null)
		{
			System.out.println("FALSE COMMIT");
			return;
		}
		
		for (int i = 0; i < transactionRecords.size(); i++)
		{
			RecordNode aRecord = transactionRecords.get(i);
			int aValue = aRecord.getValue();
			String aKey = aRecord.getName();
			if (all_values.contains(aValue))
			{
				// a value already exists in db
				// append RecordNode after the first node with such value
				getFirstWithValue(all_records, aValue).setNext(aRecord);
			}else
			{
				all_values.add(new Integer(aValue));
			}
			all_records.put(aKey, aRecord);
		}
		
		transactionCommandPointer = null;
		transactionRecords = null;
	}


	private void dbRollBack(CommandNode aCmd) {
		if (transactionCommandPointer == null)
		{
			System.out.println("INVALID ROLLBACK");
			return;
		}
		
		boolean hitBegin = false;
		while(transactionCommandPointer != null && !hitBegin)
		{
			hitBegin = reverseProcessing(transactionCommandPointer);
			transactionCommandPointer = transactionCommandPointer.getPrevious();
		}
	}
	
	// reversely handles only the meaningful command, i.e. SET & UNSET
	// return true when the aCmd is a BEGIN
	private boolean reverseProcessing(CommandNode aCmd)
	{
		switch (aCmd.getCommandId()) {
			case CommandNode.SET:
				int index = findWithNameInTransaction(aCmd.getName());
				if (index >= 0)
				{
					transactionRecords.remove(index);
				}else
				{
					System.out.println("Error, any SET in a transaction should store at arraylist");
				}
				break;
			case CommandNode.UNSET:
				reverUnset(aCmd);
				break;
			case CommandNode.BEGIN:
				return true;
			default:
				break;
		}
		return false;
	}

	
	private void reverUnset(CommandNode aCmd) {
		if (aCmd.getCommandId() != CommandNode.UNSET)
		{
			return;
		}
		
		String aKey = aCmd.getName();
		int aValue = aCmd.getValue();
		RecordNode aRec= new RecordNode(aKey, aValue);
		// before this step, the aKey should not be present in both arraylist and hashtable 
		if (aCmd.isModifiedFromPersist())
		{	
			if (all_values.contains(aValue))
			{
				// a value already exists in db
				// append RecordNode after the first node with such value
				getFirstWithValue(all_records, aValue).setNext(aRec);
			}else
			{
				all_values.add(new Integer(aValue));
			}
			all_records.put(aKey, aRec);
		}else
		{
			transactionRecords.add(aRec);
		}
	}


	private void dbTranBegin(CommandNode aCmd) {
		if (transactionCommandPointer == null)
		{
			transactionCommandPointer = aCmd;
			transactionRecords = new ArrayList<RecordNode>();
		}else
		{
			transactionCommandPointer.setNext(aCmd);
			transactionCommandPointer = transactionCommandPointer.getNext();
		}
	}


	private void dbSet(CommandNode aCmd) {
		String name = aCmd.getName();
		int value = aCmd.getValue();
		
		RecordNode aRecord = new RecordNode(name, value);
		if (aRecord != null)
		{
			if (transactionCommandPointer == null)
			{
				
				Integer trial_value = new Integer(aRecord.getValue());
				if (all_values.contains(trial_value))
				{
					if (all_records.get(name) == null)
					{
						// if this is a record with new key entry and value already exists in db
						// append RecordNode after the first node with such value
						getFirstWithValue(all_records, trial_value).setNext(aRecord);
					}
				}else
				{
					all_values.add(new Integer(aRecord.getValue()));
				}
				RecordNode oldNode = all_records.get(name);
				if (oldNode != null)
				{
					int oldValue = oldNode.getValue();
					if (oldValue != value )
					{
						shrinkValues(oldValue);
					}
					reconnectNode(oldNode);
				}
				all_records.put(aRecord.getName(), aRecord);
			
			}else
			{
				int indexInNewRecords = findWithNameInTransaction(name);
				if (indexInNewRecords >= 0)
				{
					RecordNode oldNode = transactionRecords.get(indexInNewRecords);
					int oldValue = oldNode.getValue();
					if (oldValue != value )
					{
						shrinkValues(oldValue);
					}
					transactionRecords.remove(indexInNewRecords);
					CommandNode unsetAction = new CommandNode(CommandNode.UNSET, name, false);
					unsetAction.setValue(oldValue);
					transactionCommandPointer.setNext(unsetAction);
					transactionCommandPointer = transactionCommandPointer.getNext();
				}
				else if (all_records.get(name) != null)
				{
					RecordNode oldNode = all_records.get(name);
					int oldValue = oldNode.getValue();
					if (oldValue != value )
					{
						shrinkValues(oldValue);
					}
					reconnectNode(oldNode);
					all_records.remove(name);
					CommandNode unsetAction = new CommandNode(CommandNode.UNSET, name, true);
					unsetAction.setValue(oldValue);
					transactionCommandPointer.setNext(unsetAction);
					transactionCommandPointer = transactionCommandPointer.getNext();
				}
				transactionRecords.add(aRecord);
				transactionCommandPointer.setNext(aCmd);
				transactionCommandPointer = transactionCommandPointer.getNext();
			}
		}
	}

	
	private void dbUnset(CommandNode aCmd) {
		String nameKey = aCmd.getName();
		
		RecordNode result = all_records.get(nameKey);
		if (result != null)
		{
			int oldValue = result.getValue();
			shrinkValues(oldValue);
			reconnectNode(result);
			all_records.remove(nameKey);
			if (transactionCommandPointer != null)
			{
				CommandNode unsetAction = new CommandNode(CommandNode.UNSET, nameKey, true);
				unsetAction.setValue(oldValue);
				transactionCommandPointer.setNext(unsetAction);
				transactionCommandPointer = transactionCommandPointer.getNext();
			}
		}else
		{
			int indexInTran = findWithNameInTransaction(nameKey);
			if (indexInTran >= 0)
			{
				result = findInTransaction(nameKey);
				int oldValue = result.getValue();
				shrinkValues(oldValue);
				transactionRecords.remove(indexInTran);
				CommandNode unsetAction = new CommandNode(CommandNode.UNSET, nameKey, false);
				unsetAction.setValue(oldValue);
				transactionCommandPointer.setNext(unsetAction);
				transactionCommandPointer = transactionCommandPointer.getNext();
			}else
			{
				System.out.println("Not Found, can't unset");
			}
		}
	}


	private void reconnectNode(RecordNode oldNode) {
		if (oldNode.previous != null)
		{
			oldNode.previous.setNext(oldNode.next);
		}else
		{
			if (oldNode.next != null)
			{
				oldNode.next.previous = null;
			}
		}
	}
	
	private void shrinkValues(int oldValue) {
		if (countRecord(oldValue) == 1)
		{
			all_values.remove(new Integer(oldValue));
		}
	}


	private void dbGet(String key) {
		RecordNode result = all_records.get(key);
		if (result != null)
		{
			System.out.println(result.getValue());
		}else
		{
			result = findInTransaction(key);
			if (result != null)
			{
				System.out.println(result.getValue());
			}else
			{
				System.out.println("NULL");
			}
		}
	}
	
	private RecordNode findInTransaction(String keyValue)
	{
		if (transactionRecords == null)
		{
			return null;
		}
		
		for (int i = 0; i < transactionRecords.size(); i++)
		{
			if (transactionRecords.get(i).getName().equals(keyValue))
			{
				return transactionRecords.get(i);
			}
		}
		
		return null;
	}


	private int dbGetCount(int value) {
		int recordCountResult = countRecord(value);
		
		if (transactionRecords == null)
		{
			return recordCountResult;
		}
		
		for (int i = 0; i < transactionRecords.size(); i++)
		{
			if (transactionRecords.get(i).getValue() == value)
			{
				recordCountResult++;
			}
		}
		return recordCountResult;
	}

	public static CommandNode makeCommand(String input)
	{
		String[] content = input.split(" ");
		if (content.length < 1)
		{
			System.out.println("Invalid Command");
			return null;
		}
		
		if (content[0].equals("SET") && content.length == 3)
		{
			return new CommandNode(CommandNode.SET, content[1], Integer.parseInt(content[2]));
		}
		else if (content[0].equals("GET") && content.length == 2)
		{
			return new CommandNode(CommandNode.GET, content[1]);
		}
		else if (content[0].equals("UNSET") && content.length == 2)
		{
			return new CommandNode(CommandNode.UNSET, content[1]);
		}
		else if (content[0].equals("NUMEQUALTO") && content.length == 2)
		{
			return new CommandNode(CommandNode.NUMEQUALTO, Integer.parseInt(content[1]));
		}
		else if (content[0].equals("BEGIN") && content.length == 1)
		{
			return new CommandNode(CommandNode.BEGIN);
		}
		else if (content[0].equals("ROLLBACK") && content.length == 1)
		{
			return new CommandNode(CommandNode.ROLLBACK);
		}
		else if (content[0].equals("COMMIT") && content.length == 1)
		{
			return new CommandNode(CommandNode.COMMIT);
		}else
		{
			System.out.println("Invalid Command");
			return null;
		}
	}
	
	public static RecordNode makeRecord(String input)
	{
		String[] content = input.split(" ");
		if (content.length != 2)
		{
			System.out.println("Error making a Record, Invalid Data Format!");
			return null;
		}
		int rValue = Integer.parseInt(content[1]);
		return (new RecordNode(content[0], rValue));
	}
	
	// normal this is invoked when it's certain that there exist a node with inputV to reduce the cost
	public static RecordNode getFirstWithValue(Hashtable<String, RecordNode> table, int inputV)
	{
		Enumeration<String> e = table.keys();
		while (e.hasMoreElements())
		{
			String aKey = e.nextElement();
			RecordNode currentNode = table.get(aKey);
			if (currentNode.getValue() == inputV)
			{
				return currentNode;
			}
		}
		return null;
	}
	
	public int countRecord(int rValue)
	{
		
		if (!all_values.contains(rValue))
		{
			return 0;
		}
		
		Enumeration<String> e = all_records.keys();
		int counter = 0;
		while (e.hasMoreElements())
		{
			String aKey = e.nextElement();
			if (all_records.get(aKey).getValue() == rValue)
			{
				counter = 1 + countAdjNode(all_records.get(aKey));
				break;
			}
		}
		return counter;
	}
	
	private int countAdjNode(RecordNode a)
	{
		int adjCount = 0;
		RecordNode pre = a.previous;
		while (pre != null)
		{
			adjCount ++;
			pre = pre.previous;
		}
		RecordNode next = a.next;
		while (next != null)
		{
			adjCount++;
			next = next.next;
		}
		return adjCount;
	}
	
	private int findWithNameInTransaction(String name) 
	{
		if (transactionRecords == null)
		{
			return -1;
		}
		
		for (int i = 0; i < transactionRecords.size(); i++)
		{
			if (transactionRecords.get(i).getName().equals(name))
			{
				return i;
			}
		}
		return -1;
	}

	
	public boolean isTerminated() {
		return terminates;
	}

	public void setTerminates(boolean terminates) {
		this.terminates = terminates;
	}


	public Hashtable<String, RecordNode> getAll_records() {
		return all_records;
	}
	
	public void printTable()
	{
		Enumeration<String> e = all_records.keys();
		while (e.hasMoreElements())
		{
			String aKey = e.nextElement();
			System.out.println("Key is: " + aKey + ", value is: " + all_records.get(aKey).getValue());
		}
	}

}



public class SimpleTrieNode {

	/**
	 * @param args
	 */
	public SimpleTrieNode prev;
	public SimpleTrieNode next;
	public SimpleTrieNode[] subNodes;
	public char[] values;
	public char sValue;
	public boolean isWord; // true indicate the node contains a word in our dictionary
	
	public SimpleTrieNode()
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
	}
	
	public SimpleTrieNode(String word)
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
		values = word.toCharArray();
		if (values.length >= 1)
		{
			sValue = values[values.length-1];
		}
	}
	
	
	public String toString()
	{
		if (values == null)
			return "";
		
		return new String(values);
	}
}

A short practice to write a trie with LinkedList for all the valid words

Trie with LinkedList

Java