-
Notifications
You must be signed in to change notification settings - Fork 0
/
1_1.cpp
92 lines (78 loc) · 1.84 KB
/
1_1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//
// 1_1.cpp
//
//
// Created by Pengyan Qin on 6/13/15.
//
//
# include <string>
# include <iostream>
# include <algorithm> // for transform
using namespace std;
// time complexity: O(n)
// 易错点:don't consider the special case
// s.lengt() > 128
bool is_unique1(string s){ // ASCII string
if(s.length() > 128)
return false;
int a[128] = {0};
for(int i = 0; i < s.length(); ++i){
int num = (int)s[i];
if(a[num])
return false;
else
a[num] = 1;
}
return true;
}
bool is_unique2(string s){// only english word
if(s.length() > 26)
return false;
int a[26] = {0};
transform(s.begin(), s.end(), s.begin(), ::tolower);
for(int i = 0; i < s.length(); ++i){
int num = s[i] - 'a';
if(a[num])
return false;
else
a[num] = 1;
}
return true;
}
bool is_unique3(string s){ // use less space for only english word
if(s.length() > 26)
return false;
int a = 0; // 32 bits
transform(s.begin(), s.end(), s.begin(), ::tolower);
for(int i = 0; i < s.length(); ++i){
int num = s[i] - 'a';
if(a & (1 << num))
return false;
else
a |= (1 << num);
}
return true;
}
bool is_unique4(string s){ // use less space for ASCII string
if(s.length() > 128)
return false;
int a[4] = {};
for(int i = 0; i < s.length(); ++i){
int num = (int)s[i];
int shift = num%32;
int ind = num/32;
if(a[ind] & (1 << shift))
return false;
else
a[ind] |= (1 << shift);
}
return true;
}
int main(){
string str = "absgs";
cout << is_unique4(str) << endl;
cout << is_unique1(str) << endl;
string str1 = "AbowjHP";
cout << is_unique3(str1) << endl;
return 0;
}