Skip to content

Instantly share code, notes, and snippets.

@youchen

youchen/cc150_01_01.java

Last active August 29, 2015 14:02
Download ZIP

Revisions

  1. Youchen revised this gist Jun 17, 2014. 1 changed file with 38 additions and 1 deletion.
    39 changes: 38 additions & 1 deletion cc150_01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -17,16 +17,26 @@
    * My algorithm check n times for the string. so that is O(n)?
    * I am not sure with the analysis.
    * Space Complexity: O(1)
    *
    */
    public class cc150_01_01{

    public static void main(String[] args) {
    System.out.println("Version 1: ");
    System.out.println(cc150_01_01.allCharUnique("abcdefghijklmnopqrstuvwxyz!@#$%^&*()"));//prints "true"
    System.out.println(cc150_01_01.allCharUnique("abcdefghii"));//prints "false"
    System.out.println(cc150_01_01.allCharUnique("!@"));//prints "true"

    System.out.println("\nVersion 2: ");
    System.out.println(cc150_01_01.allCharUnique2("abcdefghijklmnopqrstuvwxyz!@#$%^&*()"));//prints "true"
    System.out.println(cc150_01_01.allCharUnique2("abcdefghii"));//prints "false"
    System.out.println(cc150_01_01.allCharUnique2("!@"));//prints "true"
    }

    /*
    * 1. your code does not handle the corner case for empty string/null string
    * 2. you can use a hash set for this solution, no need for <key, value> pair here,
    * the key itself is the value.
    */
    public static boolean allCharUnique(String str){
    //make a hash table to store the char of string
    Hashtable<Integer, Character> charMap = new Hashtable<Integer, Character>(str.length());
    @@ -45,4 +55,31 @@ public static boolean allCharUnique(String str){
    }
    return true;
    }
    /**
    * revised version
    * @param str the String for checking
    * @return true if it include the unique character, otherwise false.
    */
    public static boolean allCharUnique2(String str){
    //corner case:
    if (str.isEmpty()) {
    return true;
    }
    //make a hash set to store the char of string
    HashSet<Character> charMap = new HashSet<Character>(str.length());

    //add the 1st char to the hash set
    charMap.add(str.charAt(0));

    //keep adding until the end
    for(int i = 1; i < str.length(); i++){
    //check if there is already existing the char
    if (charMap.contains(str.charAt(i) ) ) {
    return false;
    }
    //if not, add it to the hash set
    charMap.add(str.charAt(i));
    }
    return true;
    }
    }
  2. Youchen revised this gist Jun 17, 2014. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion cc150_01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -16,7 +16,8 @@
    * 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)
    * Space Complexity: O(1)
    *
    */
    public class cc150_01_01{

  3. Youchen revised this gist Jun 17, 2014. 1 changed file with 10 additions and 4 deletions.
    14 changes: 10 additions & 4 deletions cc150_01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,4 @@
    import java.util.*;
    /**
    * 1.1 Implement an algorithm to determine if a string has all unique characters.
    * What if you cannot use additional data structures?
    @@ -20,20 +21,25 @@
    public class cc150_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("!@"));
    System.out.println(cc150_01_01.allCharUnique("abcdefghijklmnopqrstuvwxyz!@#$%^&*()"));//prints "true"
    System.out.println(cc150_01_01.allCharUnique("abcdefghii"));//prints "false"
    System.out.println(cc150_01_01.allCharUnique("!@"));//prints "true"
    }

    public static boolean allCharUnique(String str){
    //make a hash table to store the char of string
    Hashtable<Integer, Character> charMap = new Hashtable<Integer, Character>(str.length());


    //add the 1st char to the hash table
    charMap.put(0, str.charAt(0));

    //keep adding until the end
    for(int i = 1; i < str.length(); i++){
    //check if there is already existing the char that is adding to
    if (charMap.containsValue(str.charAt(i) ) ) {
    return false;
    }
    //if not, add it to the hash table
    charMap.put(i, str.charAt(i));
    }
    return true;
  4. Youchen revised this gist Jun 17, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion cc150_01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -17,7 +17,7 @@
    * I am not sure with the analysis.
    * Space Complexity: ?(don't know)
    */
    public class _01_01 {
    public class cc150_01_01{

    public static void main(String[] args) {
    System.out.println(_01_01.allCharUnique("abcdefghijklmnopqrstuvwxyz!@#$%^&*()"));
  5. Youchen renamed this gist Jun 17, 2014. 1 changed file with 0 additions and 0 deletions.
    0 _01_01.java → cc150_01_01.java
    View file
    File renamed without changes.
  6. Youchen revised this gist Jun 17, 2014. 1 changed file with 20 additions and 5 deletions.
    25 changes: 20 additions & 5 deletions _01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,22 @@
    package cc150;

    import java.util.*;

    /**
    * 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) {
    @@ -19,7 +34,7 @@ public static boolean allCharUnique(String str){
    if (charMap.containsValue(str.charAt(i) ) ) {
    return false;
    }
    charMap.put(i, str.charAt(i));//add(i, str.charAt(i));
    charMap.put(i, str.charAt(i));
    }
    return true;
    }
  7. Youchen created this gist Jun 17, 2014.
    26 changes: 26 additions & 0 deletions _01_01.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,26 @@
    package cc150;

    import java.util.*;

    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));//add(i, str.charAt(i));
    }
    return true;
    }
    }