给两个字符串s1和s2,给出一个算法来查找S1中的所有字符,这些字符也在S2中

Question

示例:

S1:abcde S2:cdef

答案:cde

Answer 1

假设与潜在的字符串长度相比,字符集很小且有限,这是合理的.因此,例如处理8位字符(在粗略的C++伪代码中):

bool in_a[256] = { false };
bool in_b[256] = { false };
for (int i = 0; i < a.size(); ++i)
    in_a[a[i]] = true;
for (int i = 0; i < b.size(); ++i)
    in_b[b[i]] = true;
// and in_a and in_b
for (int i = 0; i < b.size(); ++i)
    if (in_a[i] && in_b[i])
    {
        std::cout << i;
        if (isprint(i)) std::cout << '\'' << (char)i << '\'';
        std::cout << ' ';
    }
std::cout << '\n';

请注意,使用哈希表而不是数组是一个巨大的浪费时间(除非处理说32位字符表示).

Yordan的评论中提出了简化的实现.这避免了最终循环从0..255并且只需要一个跟踪数组.结果的顺序是未排序的.

#include <vector>
#include <iostream>

int main()
{
    std::string a = "abdcdefg";
    std::string b = "byfdz";
    bool track[256] = { false };
    for (int i = 0; i < a.size(); ++i)
        track[a[i]] = true;
    for (int i = 0; i < b.size(); ++i)
        if (track[b[i]])
        {
            track[b[i]] = false; // don't match again
            std::cout << (int)b[i];
            if (isprint(b[i])) std::cout << " \'" << (char)(b[i]) << "\'";
            std::cout << ' ';
        }
    std::cout << '\n';
}