[題目]
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structure?
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structure?
給一個string s，問你s中的所有char是否都沒有重複出現過，return true or false
[思路]
method 1.暴力法:
所謂重複就是"A等於B"，因此我們先設定
A=s[0], B=s[1]~s[n-1]， 比對A,B是否相等
A=s[1], B=s[2]~s[n-1]， 比對A,B是否相等
A=s[2], B=s[3]~s[n-1]， 比對A,B是否相等
...
A=s[n-2], B=s[n-1]， 比對A,B是否相等
如果上述測試任何一組A,B相等就return false
全部都不相等就return true
時間複雜度是O(n^2)
method 2.Sort
若將string中的字母先sort過，相同的字母就會排在一起
接著只要for loop一遍, 比較str[i]與str[i+1]是否相等就好
時間複雜度是O(n log n)
method 3.統計法: <--最快, 但須要額外的structure
這是一個常常出現在"出現幾次/有沒有重複出現"的問題中的解決方案。我們把s爬過一遍，統計每個char出現的次數，若任何人出現次數大於1，就return false，若沒有人則return true。
聽起來很簡單，但關鍵問題在你如何把"統計"這個的行為做的有效率。統計法的時間複雜度是O(n*更新count所需時間)，如果你使用很蠢的資料結構來更新count，那麼將不比暴力法快。例如你建了一張表
a,1
g,1
h,1
t,1
此時當看到一個新的char 'y'，你要找到'y'所對應的count然後把它加一，你必須要從上到下將表掃描一遍，然後發現y不存在，接著把y,1插入表中，這花了o(n)的時間。n個char的總時間複雜度是O(n^2)。根本沒有比較快。
所以關鍵問題是如何有效地執行統計(更新count) ? 答案是用hash table
hash table 的好處是可以O(1)找到key所對應的欄位。這個題目中key就是char，以上例來說key='y' , 找尋'y'所在的欄位只要O(1)。因此n個char的總時間複雜度是O(n*1)。
更具體地說，c++裡面可以用
unordered_map<char,int> hashtable;
//或是
int table[256];
來作為hash table。當你要更新'y'的count時，直接寫即可。
table['y'-'a']++;
