Menu
I was looking through the cracking the coding interview book solutions and noticed the following problem:
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
This was one of the solutions provided:
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
Why is the char_set array initialized with a size of 256? I was thinking that it was because there are 128 ascii characters but I'm not sure. Also, this solution seems to be in Java, but would an initial size also be necessary if this was done in C++?
824
#define NO_OF_CHARS 256 // This function returns true if both arrays are same. // Irrespective of the size of patternText, this functions takes O(256) time i.e., O(1) time complexity.
You do not need to initialize all elements in an array. If an array is partially initialized, elements that are not initialized receive the value 0 of the appropriate type. The same applies to elements of arrays with static storage duration.
Array Initialization in Java To use the array, we can initialize it with the new keyword, followed by the data type of our array, and rectangular brackets containing its size: int[] intArray = new int[10]; This allocates the memory for an array of size 10 . This size is immutable.
Even if you do not initialize the array, the Java compiler will not give any error. Normally, when the array is not initialized, the compiler assigns default values to each element of the array according to the data type of the element. We will demonstrate these default values using the following program.
I was thinking that it was because there are 128 ascii characters but I'm not sure.
No. With extended ASCII codes, there are a total 256 characters. That's the reason for 256.
http://www.asciitable.com/
Apart from the reason given for 256, please note that com/
Note that as Erwin Bolwidt said, the code is at best incomplete in any case, because Java "characters" are not ASCII nor extended ASCII. They are "a 16-bit Unicode character", so the array should have been new boolean[65536]
67
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
