#include <bits/stdc++.h>
using namespace std;
class Trie {
private:
static const int chars = 26;
Trie* child[chars];
bool isLeaf{};
public:
Trie() {
memset(child, 0, sizeof(child));
}
vector<string>myWords;
~Trie() {
for (int i = 0; i < chars; i++) {
if (child[i]) {
delete child[i];
}
}
}
void insert(const string& s, int idx = 0) {
if (idx == s.length()) {
isLeaf = true;
} else {
int cur = s[idx] - 'a';
if (child[cur] == nullptr) {
child[cur] = new Trie();
}
child[cur]->insert(s, idx + 1);
}
myWords.push_back(s);
}
vector<string> autoComplete(const string &s){
vector<string>ans;
for(auto w : myWords){
if(w.substr(0,s.length()) == s){
ans.push_back(w);
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
int main() {
Trie tree;
tree.insert("abcd");
tree.insert("ab");
tree.insert("abx");
tree.insert("abyz");
tree.insert("xyz");
tree.insert("a");
tree.insert("bcd");
vector<string>res;
res = tree.autoComplete("ab");
for(auto &str:res){
cout<<str<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBUcmllIHsKcHJpdmF0ZToKICAgIHN0YXRpYyBjb25zdCBpbnQgY2hhcnMgPSAyNjsKICAgIFRyaWUqIGNoaWxkW2NoYXJzXTsKICAgIGJvb2wgaXNMZWFme307CgpwdWJsaWM6CiAgICBUcmllKCkgewogICAgICAgIG1lbXNldChjaGlsZCwgMCwgc2l6ZW9mKGNoaWxkKSk7CiAgICB9CiAgICB2ZWN0b3I8c3RyaW5nPm15V29yZHM7CiAgICB+VHJpZSgpIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGNoYXJzOyBpKyspIHsKICAgICAgICAgICAgaWYgKGNoaWxkW2ldKSB7CiAgICAgICAgICAgICAgICBkZWxldGUgY2hpbGRbaV07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgdm9pZCBpbnNlcnQoY29uc3Qgc3RyaW5nJiBzLCBpbnQgaWR4ID0gMCkgewogICAgICAgIGlmIChpZHggPT0gcy5sZW5ndGgoKSkgewogICAgICAgICAgICBpc0xlYWYgPSB0cnVlOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGludCBjdXIgPSBzW2lkeF0gLSAnYSc7CiAgICAgICAgICAgIGlmIChjaGlsZFtjdXJdID09IG51bGxwdHIpIHsKICAgICAgICAgICAgICAgIGNoaWxkW2N1cl0gPSBuZXcgVHJpZSgpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGNoaWxkW2N1cl0tPmluc2VydChzLCBpZHggKyAxKTsKICAgICAgICB9CiAgICAgICAgbXlXb3Jkcy5wdXNoX2JhY2socyk7CiAgICB9CgoKICAgIHZlY3RvcjxzdHJpbmc+IGF1dG9Db21wbGV0ZShjb25zdCBzdHJpbmcgJnMpewogICAgICAgIHZlY3RvcjxzdHJpbmc+YW5zOwogICAgICAgIGZvcihhdXRvIHcgOiBteVdvcmRzKXsKICAgICAgICAgICAgaWYody5zdWJzdHIoMCxzLmxlbmd0aCgpKSA9PSBzKXsKICAgICAgICAgICAgICAgIGFucy5wdXNoX2JhY2sodyk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgc29ydChhbnMuYmVnaW4oKSwgYW5zLmVuZCgpKTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgICBUcmllIHRyZWU7CiAgICB0cmVlLmluc2VydCgiYWJjZCIpOwogICAgdHJlZS5pbnNlcnQoImFiIik7CiAgICB0cmVlLmluc2VydCgiYWJ4Iik7CiAgICB0cmVlLmluc2VydCgiYWJ5eiIpOwogICAgdHJlZS5pbnNlcnQoInh5eiIpOwogICAgdHJlZS5pbnNlcnQoImEiKTsKICAgIHRyZWUuaW5zZXJ0KCJiY2QiKTsKICAgIHZlY3RvcjxzdHJpbmc+cmVzOwogICAgcmVzID0gdHJlZS5hdXRvQ29tcGxldGUoImFiIik7CgogICAgZm9yKGF1dG8gJnN0cjpyZXMpewogICAgICAgIGNvdXQ8PHN0cjw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==