cc150 - 1.1 UniqueCharChecker

cc150_01_01.java

/**
 * 1.1 Implement an algorithm to determine if a string has all unique characters. 
 * 	What if you cannot use additional data structures? 
 * 
 * idea: Make a hash table to store the character.
 * 	 The key is the position of the char in the given string;
 * 	 The value is the char in the given string.
 * By adding the char of the given string into the hash table, first check
 * 	 if the hash table has already contain the value(the particular char in String).
 * If the hash table contains a particular value, meaning the char which is adding has 
 * 	 occured before, return false;
 * 	 otherwise, return true;
 * 
 * Time Complexity: O(n)
 * 	Since the method of "containValue" of hash table takes constant time: O(1),
 * 	My algorithm check n times for the string. so that is O(n)?
 * 	I am not sure with the analysis.
 * Space Complexity: ?(don't know)
 */
public class _01_01 {
	
	public static void main(String[] args) {
		System.out.println(_01_01.allCharUnique("abcdefghijklmnopqrstuvwxyz!@#$%^&*()"));
		System.out.println(_01_01.allCharUnique("abcdefghii"));
		System.out.println(_01_01.allCharUnique("!@"));
	}
	
	public static boolean allCharUnique(String str){
		Hashtable<Integer, Character> charMap = new Hashtable<Integer, Character>(str.length());

		charMap.put(0, str.charAt(0));
		
		for(int i = 1; i < str.length(); i++){
			if (charMap.containsValue(str.charAt(i)  )  ) {
				return false;
			}
			charMap.put(i, str.charAt(i));
		}
		return true;
	}
}