-
Notifications
You must be signed in to change notification settings - Fork 4
/
IsUnique.java
35 lines (31 loc) · 863 Bytes
/
IsUnique.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
Cracking the Coding Interview: Problem 1.1
Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
*/
/*
Note that doing without any additional data structures would likely require either brute force (check for every letter if it matches to
another letter) or by sorting the String (provided the input could be manipulated) and then comparing neighboring elements for equality
*/
class Solution
{
public boolean isUnique(String s)
{
if (s.length() > 256)
{
return false;
}
// only 256 unique characters possible
boolean[] appeared = new boolean[256];
for (int i = 0; i < s.length(); i++)
{
int value = s.charAt(i);
if (appeared[value])
{
return false;
// we know its already appeard
}
appeared[value] = true;
}
return true;
}
}