andre ahmed andre ahmed - 9 days ago 6
C++ Question

Check if a vector of strings is a substring in one of elements

I have a vector of strings like

a1 = ["arp", "live", "strong"]

a2 = ["lively", "alive", "harp", "sharp", "armstrong"]


How would I check if armstrong is a substring of strong in a1. using C++

I would do two for loops and check if a string is a substring in a2, but I want an efficient approach.

std::vector<std::string> inArray(std::vector<std::string> &array1, std::vector<std::string> &array2)
{
vector<string> result;
for (string &s : array1)
{
for (string &d : array2)
{

if (s.find(d) != string::npos)
{
cout << d << endl;
}
}

}

return result;

}

int main() {

vector<string> a = { "arp", "live", "strong" };
vector<string> b = { "lively", "alive", "harp", "sharp", "armstrong" };

vector<string> result = inArray(a, b);

}


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.

Example 1:

a1 = ["arp", "live", "strong"]

a2 = ["lively", "alive", "harp", "sharp", "armstrong"]

returns ["arp", "live", "strong"]

Answer

First: Use names for the variables and functions that make it easy to identify the purpose

Second: A vector will not magically fill itself.

Third: You are currently searching for the full strings within the substrings (see first)

Fourth: Pass the value by const reference if you don't plan on modifying it.

Fifth: According to your expected answer you don't want duplicates. I would suggest using std::set for this purpose as it doesn't allow duplicates.

#include <vector>
#include <set>
#include <string>
#include <iostream>

using std::set;
using std::vector;
using std::string;
using std::cout;

set<string> getMatchingSubstrings(const vector<string> &subStrings, const vector<string> &fullStrings)
{   
    set<string> result;
    for (const string &fullString : fullStrings)
    {
        for (const string &subString : subStrings)
        {
            if (fullString.find(subString) != string::npos)
            {
                result.insert(subString);
            }
        }

    }
    return result;
}

int main() {

    vector<string> a = { "arp", "live", "strong" };
    vector<string> b = { "lively", "alive", "harp", "sharp", "armstrong" };
    set<string> result = getMatchingSubstrings(a, b);
}

A slightly faster approach might be remove the already found substrings from the initial list so you don't have to check for these twice. In this case the result won't be sorted, so if you need to sort again this might not be the best choice.

#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::string;
using std::cout;

std::vector<std::string> getMatchingSubstrings(const std::vector<std::string> &subStrings, const std::vector<std::string> &fullStrings)
{   
    vector<string> unmatchedSubStrings = subStrings;
    vector<string> matchedSubStrings;
    for (const string &fullString : fullStrings)
    {
        if (unmatchedSubStrings.empty()) break;
        for (auto subStringIter = unmatchedSubStrings.begin(); subStringIter != unmatchedSubStrings.end();)
        {
            const string& subString = *subStringIter;
            if (fullString.find(subString) != string::npos)
            {
                matchedSubStrings.push_back(subString);
                subStringIter = unmatchedSubStrings.erase(subStringIter);
            }
            else
            {
                ++subStringIter;
            }
        }
    }

    return matchedSubStrings;
}

int main() {

    vector<string> a = { "arp", "live", "strong" };
    vector<string> b = { "lively", "alive", "harp", "sharp", "armstrong" };

    vector<string> result = getMatchingSubstrings(a, b);

}
Comments