跪求各位大佬,帮忙看下为什么会段错误?
美团点评2020校招系统开发方向笔试题 最后一题 求所有字符串的公共前缀。
对了 55.6% 。不知道问题出在哪?
// #include<iostream> #include<vector> #include<string> #include<unordered_map> using namespace std; //步骤1.将所有的输入string挂到树上。 //步骤2.遍历每个string,从头结点开始找到唯一前缀。 struct Node { int count; char c; unordered_map<char,Node*> m; Node(int count_) { c = ' '; count = count_; } }; int main() { int n = 0; cin >> n; vector<string> input(n); Node root(0); for (int i = 0; i < n; ++i) { cin >> input[i];//将字符串挂到树上。 Node* p = &root; root.count++; for (int j = 0; j < input[i].size(); ++j) { if (!p->m.count(input[i][j])) { p->m[input[i][j]] = new Node(1); p->m[input[i][j]]->c = input[i][j]; } else p->m[input[i][j]]->count++; p = p->m[input[i][j]]; } }//得到所有的字符串。 将所有的字符串挂到了树上。 for (int i = 0; i < n; ++i) { string tmp = input[i]; string tmpRes{}; Node* p = &root; int k = 0; while (p->m[tmp[k]]->count > 1) { //tmpRes += p->m[tmp[k]]->c; p = p->m[tmp[k]]; ++k; } tmpRes = tmp.substr(0,k+1); std::cout << tmpRes << std::endl; } return 0; }
全部评论
(0) 回帖