Implement an algorithm to determine if a string has all unique characters. With and without using extra additional data structures
/**
/**
* Implement an algorithm to determine if a string has all unique characters.
* With and without using extra additional data structures?
*
@author Sonu Mishra
*/
public class StringContainsUniqueCharacter {
/**
* Without using extra DS.
* Ignoring int variable. Time complexity is
* O(n), where n is the length of the string, and space complexity is O(n).
* We can reduce our space usage a little bit by using a bit vector.We will
* assume, in the below code, that the string is only lower case ‘a’ through
* ‘z’.This will allow us to use just a single int
*
@param str: String to check
@return : true/false
*/
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0)
return false;
checker |= (1 << val);
}
return true;
}
/**
* Using extra variable. For simplicity, assume char set is ASCII (if not,
* we need to increase the storage size.The rest of the logic would be the
* same)
*
*
@param str: String to Check
@return : true/false
*/
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;
}
public static void main(String[] args) {
System.
out.println(isUniqueChars("abcdefgh12345a678"));
System.
out.println(isUniqueChars2("154678"));
}
}
Alternatively, we could do the following:
1. Check every char of the string with every other char of the string for duplicate
occurrences.This will take O(n^2) time and no space.
2. If we are allowed to destroy the input string, we could sort the string in
O(n log* n) time and then linearly check the string for neighboring characters that are
identical.Careful, though many sorting algorithms take up extra space.
identical.Careful, though many sorting algorithms take up extra space.
0 comments:
Post a Comment