Skip to content

Instantly share code, notes, and snippets.

@jocelynzz
Created March 30, 2015 23:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jocelynzz/dd561729ee00a08f99c4 to your computer and use it in GitHub Desktop.
Save jocelynzz/dd561729ee00a08f99c4 to your computer and use it in GitHub Desktop.
CC
public class Solution {
public boolean UniqueString(String s) {
//if char has appeared before
//abcdedfe
//time complexity n^2
int len = s.length();
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (s.charAt(i) == s.charAt(j) {
return false;
}
}
}
return true;
}
}
@bxshi
Copy link

bxshi commented Mar 31, 2015

Look good to me. If you can specify the filename and change the file type to Java, then you can have cod highlight, which makes your code looks even better 😄

tl.,dr: ASCII is an integer set equals to [0,256], each value in it represents for an unique character.

As for ASCII encoding, you can treat it as a 1 to 1 mapping. For a map, there is usually two parts, one is the key, and the other one is the associated value. If we want to get the value of a key k from the given map, there are two cases:

  1. if k is in the map, it will return the value v that binds to the key
  2. if k is not in the map, then it will return something else, maybe an exception

Now with that in mind, we can treat ASCII as a map, the key is an integer, and the values are characters. Since this is a 1 to 1 mapping, the number of characters(values) in ASCII equals to the number of integers(keys) in ASCII. Therefore we use only values in the following paragraphs,

Because we know this map only contains integers in a certain range (that is because ASCII only has a limited number of characters, so does the keys), let's say N, then we can allocate N bins, each bin we tag a label from 1 to N. For each character, we throw it into the bin that has the same tag as the value. After all characters are in bins, we count the number of elements in each bin, if every bin contains zero or one element, then this is a unique string, otherwise it is not.

Hope that helps.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment