CareerCup1_1 unique characters | JYUAN
Description
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)
Tips:
1. you should check whether the String is null, or length equals 0
2. Even the extended ASCII have max 256 characters. So, if the s.length() > 256, it must have duplicate characters. Fast return false will avoid a unnecessary traverse.
Read full article from CareerCup1_1 unique characters | JYUAN
No comments:
Post a Comment