学步园

第一次写trie，WA了一次，Runtime Error两次（在释放内存的时候，开始直接data = new node[10]。。删除就出问题了。。）

至于WA，注意一下这两组数据就得了：

2

911

91

和

2

91

911

刚开始就少了一个末端的判断。

#include <iostream><br /> #include <string><br /> #include <cstring><br /> using namespace std;<br /> struct node {<br /> node* next[10];<br /> bool hasEnd;<br /> node() {<br /> for(int i = 0; i < 10; i++) next[i] = NULL;<br /> hasEnd = false;<br /> }<br /> };<br /> void _del(node* tmp) {<br /> for(int i = 0; i < 10; i++)<br /> if(tmp->next[i] != NULL) _del(tmp->next[i]);<br /> delete tmp;<br /> }<br /> int main() {<br /> int T;<br /> cin >> T;<br /> string s;<br /> while(T--) {<br /> int n;<br /> cin >> n;<br /> node* data = new node();<br /> bool ok = true;<br /> int ends = 0;<br /> for(int i = 0; i < n; i++) {<br /> cin >> s;<br /> if(ok) {<br /> node* cur = data;<br /> for(int j = 0; j < s.size() && ok; j++) {<br /> if(cur->next[s[j] - '0'] == NULL) cur->next[s[j] - '0'] = new node();<br /> //注意判断j == s.size() - 1;<br /> else if(cur->next[s[j] - '0']->hasEnd || j == s.size() - 1) ok = false;<br /> cur = cur->next[s[j] - '0'];<br /> }<br /> cur->hasEnd = true;<br /> }<br /> }<br /> if(ok) cout << "YES" << endl;<br /> else cout << "NO" << endl;<br /> _del(data);<br /> }<br /> return 0;<br /> }