查找以给定后缀结尾的字符串

什么是后缀？

在计算机科学中，后缀是指一个字符串的末尾，它不一定是整个字符串的末尾。例如，在字符串 "hello world" 中，后缀可以是 "d"，"ld"，"rld"，"orld" 等。

后缀经常用在搜索和排序算法中，例如后缀数组和后缀树等，它们可以快速查找一个字符串中特定的子串。

查找以给定后缀结尾的字符串

假设我们有一个字符串列表，我们想查找所有以给定后缀结尾的字符串。一种简单的方法是循环遍历该列表，对于每个字符串检查其末尾是否与给定后缀相同。如果相同，则将该字符串添加到结果列表中。

下面是一个使用 C++ 语言实现的示例代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> searchBySuffix(vector<string> strs, string suffix) {
    vector<string> result;
    for (string str : strs) {
        if (str.size() >= suffix.size() && str.compare(str.size() - suffix.size(), suffix.size(), suffix) == 0) {
            result.push_back(str);
        }
    }
    return result;
}
int main() {
    vector<string> strs = {"hello", "world", "leetcode", "is", "awesome"};
    string suffix = "e";
    vector<string> result = searchBySuffix(strs, suffix);
    cout << "Strings ending with '" << suffix << "':" << endl;
    for (string str : result) {
        cout << str << endl;
    }
    return 0;
}

运行结果：

Strings ending with 'e':
hello
awesome

算法分析

上述算法的时间复杂度为 O(nk)，其中 n 是字符串列表的长度，k 是给定后缀的长度。循环遍历字符串列表需要 O(n) 的时间，每个字符串的比较操作需要 O(k) 的时间。因此，总时间复杂度是 O(nk)。

如果我们使用哈希表（unordered_map）来存储字符串列表中每个字符串的结尾字符和对应的字符串，可以将时间复杂度降低到 O(n)。这是因为哈希表的查找操作时间复杂度是 O(1)。

下面是使用哈希表实现的示例代码：

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
vector<string> searchBySuffix(vector<string> strs, string suffix) {
    vector<string> result;
    unordered_map<char, vector<string>> map;
    for (string str : strs) {
        if (str.size() >= suffix.size() && str.compare(str.size() - suffix.size(), suffix.size(), suffix) == 0) {
            map[str.back()].push_back(str);
        }
    }
    if (map.find(suffix.back()) != map.end()) {
        result = map[suffix.back()];
    }
    return result;
}
int main() {
    vector<string> strs = {"hello", "world", "leetcode", "is", "awesome"};
    string suffix = "e";
    vector<string> result = searchBySuffix(strs, suffix);
    cout << "Strings ending with '" << suffix << "':" << endl;
    for (string str : result) {
        cout << str << endl;
    }
    return 0;
}

运行结果与之前相同。

结语

本文介绍了如何查找以给定后缀结尾的字符串。我们可以循环遍历字符串列表并对每个字符串进行比较，也可以使用哈希表来加速查找。无论哪种方法，时间复杂度都与字符串列表长度和给定后缀长度成正比。