CareerCup1_1 unique characters | JYUAN
Implement an algorithm to determine if a string has all unique characters.
What if you cannot use additional data structures?
Time Complexity: O(n^2)
Time Complexity: O(n)
Space Complexity: O(1)
Solution 3
Use the HashSet to fast implement. (general solution that not satisfied the Question requirement: no additional data structure)
As we all known, the Set collections cannot have same elements. So we can use the HashSet to check whether there are duplicate characters.
Tip: The HashSet data structure is based on HashTable, so there is no specific sort between elements. Which means Time Complexity of all the add(), remove() and contains() function are O(1)
Time Complexity: O(n)
Space Complexity: O(n)
Solution 4
If the interviewer told there are more than 256 characters in the string rather than just the ASCII, which means we cannot use the Boolean array to check. Is that means we must use the Solution 1 ( with Time Complexity: O(n^2))?
No! we can use another solution to solve it, but the Time Complexity will be O(nlogn):
1. using the toCharArray() method to change the string type into Char[]
2. Use the Arrays.sort() Collections to sorted the Char[] by ascending order.
3. check whether the char[i] and char[i+1] is equal, and return the result.
Tips:
1. check the char[i] and char[i+1], which means the for loop should max at charArray.length – 1 rather than length.
2. In the Arrays.sort(s) method, it use the QuickSort method to sort the char[], which means the expected Time Complexity will be O(nlogn), and the worst time will be O(n^2)
Time Complexity: O(nlogn)
Space Complexity: O(n)
Solution5：
Actually, the boolean[256] stills waste some space because maybe there are no need to use all the 256 space.
In this way, we can use bit to store the status of the character.
use Int type for example:
int has fixed size, usually 4 bytes which means 8*4=32 bits (flags). Which means, within the 256 flags, we can use an int[8] array.
Use BitSet
Read full article from CareerCup1_1 unique characters | JYUAN
Implement an algorithm to determine if a string has all unique characters.
What if you cannot use additional data structures?
Solution
Solution 1
The most inefficient way is using two loops.Time Complexity: O(n^2)
Solution 2
Assume all the input are ASCII, we can use a Boolean[] to check whether the characters in the string is duplicated. First, you can ask the interviewer whether the ASCII are 128 or extended 256, then initial a Boolean[] such as checkBoolean[256], initial each elements in the array to be false. After that, traverse all the elements, if the checkBoolean[i] == true, which means the element has been duplicated. Output False to the console and exit. Otherwise, mark the checkBoolean[i] to be true, and check the next element.Time Complexity: O(n)
Space Complexity: O(1)
Solution 3
Use the HashSet to fast implement. (general solution that not satisfied the Question requirement: no additional data structure)
As we all known, the Set collections cannot have same elements. So we can use the HashSet to check whether there are duplicate characters.
Tip: The HashSet data structure is based on HashTable, so there is no specific sort between elements. Which means Time Complexity of all the add(), remove() and contains() function are O(1)
Time Complexity: O(n)
Space Complexity: O(n)
Solution 4
If the interviewer told there are more than 256 characters in the string rather than just the ASCII, which means we cannot use the Boolean array to check. Is that means we must use the Solution 1 ( with Time Complexity: O(n^2))?
No! we can use another solution to solve it, but the Time Complexity will be O(nlogn):
1. using the toCharArray() method to change the string type into Char[]
2. Use the Arrays.sort() Collections to sorted the Char[] by ascending order.
3. check whether the char[i] and char[i+1] is equal, and return the result.
Tips:
1. check the char[i] and char[i+1], which means the for loop should max at charArray.length – 1 rather than length.
2. In the Arrays.sort(s) method, it use the QuickSort method to sort the char[], which means the expected Time Complexity will be O(nlogn), and the worst time will be O(n^2)
Time Complexity: O(nlogn)
Space Complexity: O(n)
Solution5：
Actually, the boolean[256] stills waste some space because maybe there are no need to use all the 256 space.
In this way, we can use bit to store the status of the character.
use Int type for example:
int has fixed size, usually 4 bytes which means 8*4=32 bits (flags). Which means, within the 256 flags, we can use an int[8] array.
Use BitSet
Read full article from CareerCup1_1 unique characters | JYUAN
