C++算法题-寻找相同元素

题目

codewar 的一道与字符串和数组相关的题目:

Given two arrays of strings a1 and a2 return a sorted array r in lexicographical order of the strings of a1 which are substrings of strings of a2.

提供两个数组: a1， a2。要在 a2 的每个元素中寻找是否有和 a1 其中元素相同的字符串片段，返回符合元素的数组。
示例:

Example 1:

a1 = [“arp”, “live”, “strong”]

a2 = [“lively”, “alive”, “harp”, “sharp”, “armstrong”]

returns [“arp”, “live”, “strong”]
Example 2:

a1 = [“tarp”, “mice”, “bull”]

a2 = [“lively”, “alive”, “harp”, “sharp”, “armstrong”]

returns []

1
2
3
4
5
6


class WhichAreIn
{

  public:
  static std::vector<std::string> inArray(std::vector<std::string> &array1, std::vector<std::string> &array2);
};

题解

这道题的难点在于如何寻找到相同的元素。我首先想到的是将 a2 合并成一个字符串，使用 find() 方法查找相同元素。但是发现，如果出现两个元素没有 a1 相同的元素，但是组合在一起恰巧就有。
对此不好去处理，那么只有遍历 a2 每个元素并查找是否有包含 a1 的字符串片段了。
具体操作如下:

1
2
3
4
5


for (auto src : array2) {
    for (auto target : array1) {
        if (src.find(target) < src.length()) res.emplace_back(target);
    }
}

find() 方法返回位置，而如果没有就会返回一对奇奇怪怪的数字，这使得需要让其小于 src 的长度才能添加。
如果就单靠这样返回 res 那是过不了的，实际示例有两种错误情况:

排列顺序不对排列顺序是最好解决的，使用 std::sort() 即可得到排列好的元素 :

1

std::sort(res.begin(), res.end());

重复出现元素重复出现当然需要删掉，对此略有些许复杂，我查到的方法是使用 unique() 和 erase() 函数处理。

1
2


auto it = std::unique(res.begin(), res.end());
res.erase(it, res.end());

unique() 函数将重复的元素丢到数组后面，返回重复元素的首个地址，之后用 erase() 方法进行删除就得到了最终的答案。
两个函数都是基于 c++ 迭代器实现的。
最终的答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <bits/stdc++.h>

class WhichAreIn {
   public:
    static std::vector<std::string> inArray(std::vector<std::string> &array1,
                                            std::vector<std::string> &array2) {

        std::vector<std::string> res;
        
        for (auto src : array2) {
            for (auto target : array1) {
                if (src.find(target) < src.length()) res.emplace_back(target);
            }
        }

        std::sort(res.begin(), res.end());
        auto it = std::unique(res.begin(), res.end());
        res.erase(it, res.end());
        return res;
    }
};