[cc150] 1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structure?
1.inputは「a」~「z」の26文字しかないと仮定し、最もnaive的なhashをつければよい
 

  
  
  
  

   
   
   
   
class Solution { 
   
   
   
   
public: 
   
   
   
   
    bool isUniqueChars2(string str){ 
   
   
   
   
        vector<bool> flag(26, 0); 
   
   
   
   
        for (int i = 0; i < str.size(); i++) { 
   
   
   
   
            if(flag[str[i] - 'a'] == 1) return false; 
   
   
   
   
            flag[str[i] - 'a'] = 1; 
   
   
   
   
        } 
   
   
   
   
        return true; 
   
   
   
   
    } 
   
   
   
   
         
   
   
   
   
}; 
  
  
  
  

2.この26文字以上であれば、256スペースのhashを開くのと同じように
3.もしスペースを開けられなかったら、O(n^2)の検索にしましょう
4.stringが動くならstringを並べ替えてO(nlogn)