【第四轮】3.30 - 4.5 Career Cup 1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.

按照国内的时间，已经是30号啦，所以正式开始第四轮刷题~

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

If there is any grammar error, please feel free to correct me! I really need to improve my writing.

> Most of the string / array manipulation problem can be seen as either bin sort or normal sort problem.

【解题思路】
1. If character value range is [0,256], do bin sort with normal vector or bit vector.
2. If character value range is large, e.g. unicode32, one should use set instead of vector. (not implemented)
3. Sort the string, and check if adjacency characters are the same.
【时间复杂度】
1. O(n)
2. O(nlogn) <- according to http://en.cppreference.com/w/cpp/container/set/insert
3. O(nlogn)
【空间复杂度】
1. O(1)
2. O(1)
3. O(n) or O(1), depending on if we need to keep the original string or not.
【gist link]
https://gist.github.com/bxshi/dc9a136ca248edf7e641
【test case】(optional，如果觉得比较好，欢迎贴出来分享）
A simple test case, feel free to use if you are using C/C++
https://github.com/bxshi/intervi ... c/test/1_1_test.cpp

【解题思路】
1.如果我们假设字符集是ASCII字符，那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false，遍历一遍字符串中的字符，当bool数组对应位置的值为真， 表明该字符在之前已经出现过，即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。
2. 如果不能额外的空间，一种是直接两便循环找，一种是sort后看是否相邻的元素相同，如果有相同返回false, otherwise 返回true. 不知到有些同学说过一边string如果有重复count+1这个是如何实现？

【时间复杂度】
1，O(N)
2 O(N^2)，O（NLogN）
【空间复杂度】
1.O(N)
2.O(1)
[gist link]
https://gist.github.com/songpu2015617/9ea54fad07435a202dac

【解题思路】
1、用Hash set保存出现过的每个字母，每一个字母检查一下set里有没有相同的字母，如果有则return false
2、如果是ascii字母，可以用256长的boolean数组，办法同上。
3、如果是UTF-16，开65536长boolean数组，办法同上。
4、不能用额外空间：两层嵌套loop搜索O(N^2)
5、如果给的是C之类语言的char array，而且不在乎保存输入被改变的话，可以排序之后，扫一遍，看相临位置的有没有相同字母，有则return false；

【时间复杂度】
1、2、3、O(N)
4、O(N^2)
5、O(NlogN)
【空间复杂度】
1、2、3、O(N)
4、5、O(1)
【gist link]
https://gist.github.com/n2iw/d8b52a7f67aaa553f62f
【test case】

【解题思路】
首先考虑String的编码类型，这样子决定了定义boolean数组的长度，assume使用的是ASCII，将整个字符串扫一遍来得到结果。存在的boolean为true、
思路二是也可以考虑将字符串先变成字符串数组，然后将所有元素的index设置为1，再将数组扫一遍，如果有出现过的，就--i，判断条件是if（index<0），return false
【时间复杂度】
思路一：O（n）
思路二：O（n）
【空间复杂度】
O（1），O（n）
【gist link]
https://gist.github.com/JamesJi9277/8ca1fc9a81316f40bd65
【test case】

【解题思路】
1, create an char array  for 256 ascII chars,
2, check every character from the   input string
if  the  array contains the  character   means  duplicate charactor
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/2b74fae8c0025a9a3122
【test case】
https://gist.github.com/michaelniu/2b74fae8c0025a9a3122

【解题思路】
逐个对比string内的char。
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... e-1-1-uniqchar-java

【解题思路】
1.建立一个长度256的int数组，初始化0
2.扫描字符串并计数，如果count>1返回false
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]
https://gist.github.com/A30041839/8c49221bad8df5d43247
[test case]
https://gist.github.com/A30041839/8c49221bad8df5d43247

【解题思路】
     Java中，String的每个character用ASCII编码的int值在0~255之间，建立一个初始值为false，大小为256的boolean array
     遍历整个String，如果每个character对应的table都是0（即首次看到），则所有character为unique，否则立即return false.
【时间复杂度】
      O(n)
【空间复杂度】
      O(1)
【gist link]
      https://gist.github.com/jiaodong/0d6309d1694f6e08ad83
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

[solution]
1.we can create a boolean arrary with size of 256 since there are
256 ascii character in total.
2.Then for each char in the string, we use the array to test whether
the current char existed before, if existed, return false.
3.After scanning the whole string, if no false returned, the function
will return true.

[time complexity]
O(n), n is the size of the string

[space complexity]
O(1), for the array with size of 256

[gist link]
https://gist.github.com/FionaT/029c6c4fc4c4e443517b

[test case]
""
"abca"
"abcde"
"bbb"

[solution]
Create an array of boolean with size of 256. If the length of the string is above 256, it must have duplicate character. If not, for every character in the string, set its position in the array true if it is false now. If any position is true, return false.

[time complexity]
O(n)
[space complexity]
O(1)

[gist link]
https://gist.github.com/Howiezhang226/0d0c0a2a92ea07c1fa19
[test case]
""
"  "
"abcde"
"aancasd"

【解题思路】
1.考虑只有ASICC码，建立一个长度256的boolean数组.
2.扫描字符串，得到字符的ASIC码的值，此值为index，查看boolean数组，如果true返回false，不是true就设为true.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]        Java
https://gist.github.com/LinyinWu/3a9634d00595de30aca5
[test case]
"" true
" " true
"  " false
"abc" true
"aba" false

Don't really understand ASCII. Solved this question by comparing every character to every other character.
time complexity: O(n^2)
space complexity: O(1)

gist link: https://gist.github.com/jocelynzz/dd561729ee00a08f99c4