-
-
Save Jeffwan/8857242 to your computer and use it in GitHub Desktop.
package CC150.ArraysAndString; | |
import java.util.HashSet; | |
import java.util.Set; | |
public class IsUniqueChars { | |
public static void main(String args[]) { | |
System.out.println(isUniqueChars("abcdefghijklmnopqrstuvwxyz")); | |
} | |
/** | |
* Book's solution, just use boolean[] replaces Set, I need to understand unique characters! | |
* Then I could know I can create to boolean[256] to flag exist character. | |
* | |
* In additon, no need to conver string to charArray,just use charAt(), save some space | |
* | |
* Conclusion: 1.understand unicode & ascII character.(only 256 characters) 2. study using boolean[] as flag | |
* In my solution, I just judge str == null and str.length() ==0 but not use str.length() >256 | |
* | |
*/ | |
public static boolean isUniqueChars(String str) { | |
if (str.length() > 256) { | |
return false; | |
} | |
boolean[] flag = new boolean[256]; | |
char temp; | |
for (int i=0; i<str.length(); i++) { | |
temp = str.charAt(i); | |
if(flag[temp]) { | |
return false; | |
} else { | |
flag[temp] = true; | |
} | |
} | |
return true; | |
} | |
/** | |
* Extra Data Structure Solution | |
* unique --> Set | |
*/ | |
public static boolean isUniqueChars2(String str){ | |
if (str == null) { | |
return false; | |
} | |
Set<Character> set = new HashSet<Character>(); | |
char[] arr = str.toCharArray(); | |
for (int i = 0; i < str.length(); i++) { | |
if(set.contains(arr[i])) { | |
return false; | |
} else { | |
set.add(arr[i]); | |
} | |
} | |
return true; | |
} | |
/** | |
* brute force solution | |
* No extra data structure and space but time complexity increase | |
*/ | |
public static boolean isUniqueChars3(String str) { | |
if (str == null) { | |
return false; | |
} | |
char[] arr = str.toCharArray(); | |
for (int i=0; i<arr.length; i++) { | |
for (int j=i+1; j<arr.length; j++) { | |
if (arr[i] == arr[j]) { | |
return false; | |
} | |
} | |
} | |
return true; | |
} | |
} |
Hi totoro686, You might have already understood the code by now. Just want to say what I understood from the code.
The boolean array flag[] has all its fields set to false initially.
temp has the ith character of the string stored in it.
when checking uniqueness for each character of string,
if(flag[temp]) is equivalent to if(flag[temp] == true)
It means that particular field of array has already been occupied by the character we want to check which means we are accessing that character for the second time. so we will return false.
otherwise, we are seeing that character for the first time, so now we mark the flag as true so that for the next similar character when it comes to check that field it will be shown as true (means occupied).
The solution you have will work only for ASCII characters,
What about Strings which have 6000 unique characters.
if(flag[temp]) {
return false;
} else {
flag[temp] = true;
}
what is the logical in here?
For emample:
abcdefghijklmnopqrstuvwxyz
when i = 0,
temp = str.charAt(i) mean temp = a
flag[temp] mean what?
flag[a]?
when it will return false?