Skip to content

Instantly share code, notes, and snippets.

@yokiy
Created June 17, 2014 02:04
Show Gist options
  • Save yokiy/78f19dc4d30a762cb4d9 to your computer and use it in GitHub Desktop.
Save yokiy/78f19dc4d30a762cb4d9 to your computer and use it in GitHub Desktop.
CC 1.1
#1.1 Implement an algorithm to determine if a string has all unique characters. Whatif you cannot use additional data structures?
test =[0 for i in range(255)]
re = 0
s= raw_input('Input:')
if s.strip() =='':
print'This is empty string'
else:
for i in range(0, len(s)):
val = ord(s[i])
if val in test:
print 'No, it is not unique'
break
else:
test[val] = val
re += 1
if re == len(s):
print 'Yes, it is unique'
@nealhu
Copy link

nealhu commented Jun 17, 2014

A blank space is also a character, so you shouldn't use strip().
Using "val in test" will search the whole list, the time complexity of one search is O(n), and there will be n search operations. So you are implementing an algorithm with a time complexity of O(n^2)

@yokiy
Copy link
Author

yokiy commented Jun 18, 2014

Thanks a lot! I am not sure how to use index to search a list in python

@nealhu
Copy link

nealhu commented Jun 18, 2014

There're two ways to do it. The first one is use a extra data structure, hashset(it's called set in python). It has a O(1) search time in average. The second is that, since the integer value of a character ranges from 0~255. So you can use an array of length 256, arr[i] indicating whether a char with integer value i is visited before.

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