ZBLOG

实通过字符串前缀从数组中找出搜索建议列表,写出你知道的所有实现方式,代码尽可能简洁,用C++实现

以下是几种用C++实现的方式,通过字符串前缀从数组中找出搜索建议列表:

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5. // 方法一:线性搜索
  6. vector<string> searchSuggestions1(const vector<string>& arr, const string& prefix) {
  7. vector<string> suggestions;
  8. for (const auto& word : arr) {
  9. if (word.substr(0, prefix.size()) == prefix) {
  10. suggestions.push_back(word);
  11. }
  12. }
  13. return suggestions;
  14. }
  15. // 方法二:二分搜索
  16. vector<string> searchSuggestions2(const vector<string>& arr, const string& prefix) {
  17. vector<string> suggestions;
  18. auto lower = lower_bound(arr.begin(), arr.end(), prefix);
  19. for (auto it = lower; it != arr.end(); ++it) {
  20. if ((*it).substr(0, prefix.size()) != prefix) break;
  21. suggestions.push_back(*it);
  22. }
  23. return suggestions;
  24. }
  25. // 方法三:Trie树(字典树)
  26. class TrieNode {
  27. public:
  28. vector<TrieNode*> children;
  29. };
  30. void insertWord(TrieNode* root, const string& word) {
  31. TrieNode* node = root;
  32. for (char ch : word) {
  33. int index = ch - 'a';
  34. if (!node->children[index]) {
  35. node->children[index] = new TrieNode();
  36. }
  37. node = node->children[index];
  38. }
  39. }
  40. void findWords(TrieNode* node, string& currentPrefix, vector<string>& result, const string& prefix) {
  41. if (result.size() == 3 || !node)
  42. return;
  43. if (!currentPrefix.empty() && currentPrefix.find(prefix) == 0)
  44. result.push_back(currentPrefix);
  45. for (int i = 0; i < 26; ++i) {
  46. if (node->children[i]) {
  47. currentPrefix.push_back('a' + i);
  48. findWords(node->children[i], currentPrefix, result, prefix);
  49. currentPrefix.pop_back();
  50. }
  51. }
  52. }
  53. vector<string> searchSuggestions3(const vector<string>& arr, const string& prefix) {
  54. TrieNode* root = new TrieNode();
  55. for (const auto& word : arr)
  56. insertWord(root, word);
  57. vector<string> suggestions;
  58. string currentPrefix;
  59. findWords(root, currentPrefix, suggestions, prefix);
  60. return suggestions;
  61. }
  62. int main() {
  63. vector<string> arr = { "apple", "banana", "orange", "pear", "pineapple" };
  64. string prefix = "app";
  65. // 方法一:线性搜索
  66. vector<string> suggestions1 = searchSuggestions1(arr, prefix);
  67. // 方法二:二分搜索
  68. sort(arr.begin(), arr.end());
  69. vector<string> suggestions2 = searchSuggestions2(arr, prefix);
  70. // 方法三:Trie树
  71. vector<string> suggestions3 = searchSuggestions3(arr, prefix);
  72. cout << "方法一(线性搜索)的结果:" << endl;
  73. for (const auto& suggestion : suggestions1) {
  74. cout << suggestion << endl;
  75. }
  76. cout << "\n方法二(二分搜索)的结果:" << endl;
  77. for (const auto& suggestion : suggestions2) {
  78. cout << suggestion << endl;
  79. }
  80. cout << "\n方法三(Trie树)的结果:" << endl;
  81. for (const auto& suggestion : suggestions3) {
  82. cout << suggestion << endl;
  83. }
  84. return 0;
  85. }

以上代码展示了三种常见的实现方式:

  1. 方法一:线性搜索。遍历数组,逐个比较字符串的前缀,将符合条件的字符串添加到结果列表中。

  2. 方法二:二分搜索。对数组进行排序,然后使用二分搜索找到第一个以指定前缀开头的字符串位置,再往后遍历直至不满足前缀要求。

  3. 方法三:Trie树(字典树)。构建一个Trie树,用于高效地存储和查找字符串。先插入所有字符串,然后通过递归查找匹配前缀的所有单词。

您可以选择其中一种方法或多种方法来实现,根据具体情况和需求选择最适合的方式。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=16160

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?