找出两个字符串共同拥有的最大字符数量

Question

找出两个字符串共同具有的最大字符数。字符是区分大小写的，即小写和大写字符被视为不同。

这是我的代码:

#include <iostream>
#include <cstring> 
using namespace std;

int main() {
    std::string a, b;
    int number_cases = 0, count = 0;
    cin >> number_cases;
    while (number_cases != 0) {
        cin >> a;
        cin >> b;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if (a[i] == b[j]) {
                    count++;
                    b[j] = '#';
                    break;
                }
            }
        }
        cout << count << endl;
        count = 0;
        --number_cases;
    }
}

但是运行需要超过1秒钟，我需要将其优化到不到1秒钟或恰好1秒钟。有什么优化技巧吗？

- user3305210

---

这更适合在CodeReview上进行。 - JBL

首先，定义“共同点”是什么。根据含义，最简单的解决方案就是对字符串进行排序，然后进行差异比较。（字符串有多长？尽管时间复杂度为O(n^2)，但我期望您的代码在正常长度的字符串下几乎瞬间完成。） - James Kanze

这是来自于正在进行的编程比赛 http://www.codechef.com/FEB14/problems/LCPESY 吗？你提到了“1秒”，我认为这个问题不应该回答。 - Aseem Goyal

Answer 1

只需对它们进行排序，然后使用set_intersection函数即可。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>

int main()
{
    std::string s1 = "Hello";
    std::string s2 = "World";

    std::sort(begin(s1), end(s1));
    std::sort(begin(s2), end(s2));

    std::string s3;
    std::set_intersection(begin(s1), end(s1), begin(s2), end(s2), std::back_inserter(s3));
    std::cout << s3.size() << ":" << s3;
}

现场示例。

注意: 如果您对唯一的重叠字符感兴趣，可以在 s3 上运行 std::unique。

- TemplateRex

---

它区分大小写吗？ - user3305210

是的（但可以通过传递适当的谓词来更改） - MSalters

Answer 2

我不确定你所说的“共同点”是什么意思，但对于我首先想到的定义，最简单的解决方案可能就是使用两个bool数组：

bool inA[256] = {};
for ( auto current = a.begin(), end = a.end(); current != end; ++ current ) {
    inA[static_cast<unsigned char>(*current)] = true;
}
bool inB[256] = {};
for ( auto current = b.begin(), end = b.end(); current != end; ++ current ) {
    inB[static_cast<unsigned char>(*current)] = true;
}
int count = 0;
for (int i = 0; i != 256; ++ i ) {
    if ( inA[i] && inB[i] ) {
        ++ count;
    }
}

当然，这做的事情与您的代码完全不同。如果您正在寻找最长公共子序列或所有子序列，则需要使用不同的算法。

- James Kanze

Answer 3

以下可能会有所帮助：

std::size_t count_letter_in_common_with_dup(const std::string& s1, const std::string& s2)
{
    std::size_t present1[256] = {};
    std::size_t present2[256] = {};

    for (unsigned char c : s1) {
        ++present1[c];
    }
    for (unsigned char c : s2) {
        ++present2[c];
    }
    std::size_t res = 0;
    for (int i = 0; i != 256; ++i) {
        res += std::min(present1[i], present2[i]);
    }
    return res;
}

- Jarod42

Answer 4

假设只有256个字符。我们可以扫描每个字符串一次，并在两个数组int [] arrayA（用于字符串A）和int [] arrayB（用于字符串B）中保留每个字符的计数。

最后，从0到255迭代遍历int [] arrayA，arrayB，并将结果添加到： result +=Min(arrayA[i],arrayB[i]); 时间复杂度为O(n + m + 256) = O(n)，其中n和m是字符串A和B的长度。

- Pham Trung