1554. Strings Differ by One Character
Given a list of strings dict where all the strings are of the same length.
Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.
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
| struct Trie {
Trie* next[26];
unordered_set<string> us;
bool eof;
Trie(): eof(true) {
memset(next, 0, sizeof(next));
}
void insert(string s, int i) {
if(s.length() == i) eof = true;
else {
if(!next[s[i]-'a']) next[s[i]-'a'] = new Trie();
next[s[i]-'a']->insert(s, i + 1);
us.insert(s);
}
}
bool search(string s, int i, bool changed) {
if(s.length() == i) return eof && changed;
if(changed) {
return us.count(s);
} else {
bool res = false;
if(next[s[i]-'a']) res = next[s[i]-'a']->search(s, i + 1, changed);
char ch = s[i];
for(int j = 0; j < 26 && !res; j++) {
if(!next[j] or s[i]-'a' == j) continue;
s[i] = 'a' + j;
res |= next[j]->search(s, i + 1, true);
}
s[i] = ch;
return res;
}
}
};
class Solution {
public:
bool differByOne(vector<string>& dict) {
Trie* trie = new Trie();
for(auto dic : dict) {
if(trie->search(dic,0,false)) return true;
trie->insert(dic,0);
}
return false;
}
};
|
