Closest Strings:Find minimum distance between 2 strings in a string array

Question

You are given a array of string followed by two words. You have to find the minimum distance between the two words in the given array of string

For example: (“the”, “quick”, “brown”, “fox”, “quick”) distance(“fox”,”the”) = 3 distance(“quick”, “fox”) = 1

Why is this code failing at the given below test case??

#include<iostream>
#include<string>
#include<bits/stdc++.h>

using namespace std;

int search(vector<string>v,string s1)
{
    for(int i=0;i<v.size();i++)
    {
        if(v[i]==s1)
        {
            return i;
        }
    }
    return -1;
}

int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<string> v;
        for(int i = 0; i < n; ++i)
        {
            string a;
            cin >> a;
            v.push_back(a);

        }
        string s1;
        cin >> s1;
        string s2;
        cin >> s2;
        int p, y;
        p = search(v, s1);
        y = search(v, s2);
        int d = abs(p-y);
        cout<<d<<endl;
    }
    return 0;
}

Wrong Answer. !!!Wrong Answer Possibly your code doesn't work correctly for multiple test-cases (TCs). The first test case where your code failed:

Input: 52 rbkiruxixlqpjkbcdctwvsogiurmicjafuiwrhhqsyiflkjqodomwfvhanvirgjydtyudgnyhweujpmxtdmsiickxyvrffri rbkiruxixlqpjkbcdctwvsogiurmicjafuiwrhhqsyiflkjqodomwfvhanvirgjydtyudgnyhweujpmxtdmsiickxyvrffri ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ffyvehskceaqevtqqectpasluasmkvdpbelhlgtqkw ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo ueimikiambnhdivnfbfigtqrckknhuefborlyaoo xgnuvsvdbcwtwahjpogvthlnvmpkbsocbcwwwubyxauwccgrtpqpw xgnuvsvdbcwtwahjpogvthlnvmpkbsocbcwwwubyxauwccgrtpqpw xgnuvsvdbcwtwahjpogvthlnvmpkbsocbcwwwubyxauwccgrtpqpw xgnuvsvdbcwtwahjpogvthlnvmpkbsocbcwwwubyxauwccgrtpqpw xgnuvsvdbcwtwahjpogvthlnvmpkbsocbcwwwubyxauwccgrtpqpw sqtfupuwqwvqwqtvqtqpytysnojdln ueimikiambnhdivnfbfigtqrckknhuefborlyaoo rbkiruxixlqpjkbcdctwvsogiurmicjafuiwrhhqsyiflkjqodomwfvhanvirgjydtyudgnyhweujpmxtdmsiickxyvrffri

Its Correct output is: 11

And Your Code's output is: 12

Answer 1

Three issues are highlighted in the modified code below:

int search(const vector<string>&v, const string& s1)  // use pass by const reference for performance here
{
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i].compare(s1) == 0) // use std::string::compare to compare two strings 
        {
            return i;
        }
    }
    return -1;
}


int main{
    /* other codes */
    p = search(v, s1);
    y = search(v, s2);
    if (p != -1 && y != -1) { // display output only when both searches are successful
        int d = abs(p - y);
        cout << d << endl;
    }
}

Edited: Using c++11 you can simplify like so:

int main() {
    string line;
    getline(cin, line);
    stringstream sstream{line};
    string word;
    vector<string> words;
    while (getline(sstream, word, ' ')) {
        words.push_back(word);
    }

    string from_string ="fox", to_string = "lamb";

    auto fromPos = std::distance(words.begin(), std::find(words.begin(), words.end(), from_string));
    auto toPos = std::distance(words.begin(), std::find(words.begin(), words.end(), to_string));

    if (fromPos != words.size() && toPos != words.size()) {
        cout << abs(fromPos - toPos) << endl;
    }
}

Answer 2

The code is failing, because you have a logical misassumption.

If you look at the given test strings, you will find out that there are a lot of very long strings (with many charcacters). This should obfuscate the fact that there are only 5 different strings in the test set.

If we replace those long strings with very short strings, for example an S and a index count, then the input will look like:

"S1", "S1", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S4", "S4", "S4", "S4", "S4", "S5"

Logically completely the same as the original, but will make reading and understanding much more difficult.

With the new representation of the test case you will immediately see the problem. There are many repetitions in this list. And, if you will give for example S1 and S2 as search words, then you will find in your code the first S1 at position 0 and the first S1 at position 2. You will calculate a distance of 2. Incorrect.

So you could assume that it would be good to always search for the last occurence of a string, but this will obviously also not work. We would compare the last S1 with the last S2. Also wrong. So, we need to compare the last found searchWord1 with the first found searchWord2.

But this will also not work, the serach strings could be given in the wrong order.

And, there could be more S1 S2 sequences somewhere else in the vector. And we would need to check them all.

All this would result in a very complex logic, and so I go for the brute force approach and compare everything with everything. So, if I find a S1, then I compare with all S2's. And I will do that for all S1's.

Please see the function below, which shows what I did. Please note. This is just one of many possibilities. Please check:

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

const std::vector<std::string> testStringVector{
"S1", "S1", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S2", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3", "S3",
"S3", "S3", "S3", "S3", "S3", "S3", "S3", "S4", "S4", "S4", "S4", "S4", "S5"
};

const std::string searchWord1{ "S3" };
const std::string searchWord2{ "S1" };

size_t minDistance(const std::vector<std::string>& stringVector, const std::string& s1, const std::string& s2)
{
    unsigned int result = UINT_MAX;
    // Compare everything with everything else
    for (size_t i = 0; i < stringVector.size(); ++i) {
        // Find the string s1
        if (stringVector[i] == s1) {
            for (size_t k = 0; k < stringVector.size(); ++k) {
                // Do not compare to itself
                if ((i != k) && (stringVector[k] == s2)) {
                    unsigned int distance = std::abs(static_cast<int>(i) - static_cast<int>(k));
                    if (distance < result)
                        result = distance;
                }
            }
        }
    }
    return result;
}

int main()
{
    std::cout << "\nMin Distance for '" << searchWord1 << "' and '" << searchWord2 << " is: "
        << minDistance(testStringVector, searchWord1, searchWord2) << "\n";
    return 0;
}

Answer 3

I hope I understood your question well, and if so, then this might just work (not sure though as I tested it only with simple cases). I added comments to the code instead of explaining it here. Hope it's not a problem.

#include <vector>
#include <string>
#include <limits>


class MinimalDistance
{
private:
    const std::vector<std::string> words;
    struct indexed_word
    {
        unsigned int index;
        std::string word;

        indexed_word() {}
        indexed_word(unsigned int index, const std::string& word) : index(index), word(word) {}

        bool operator<(const indexed_word& iw) const
        { return this->index < iw.index; }
        bool operator>(const indexed_word& iw) const
        { return this->index > iw.index; }
        bool operator==(const indexed_word& iw) const
        { return this->index == iw.index; }
        bool operator<=(const indexed_word& iw) const
        { return this->index <= iw.index; }
        bool operator>=(const indexed_word& iw) const
        { return this->index >= iw.index; }

        int operator-(const indexed_word& iw) const
        { return static_cast<int>(this->index) - static_cast<int>(iw.index); }

        bool operator==(const std::string& s) const
        { return this->word == s; }

        int operator=(const indexed_word& iw) const
        { return static_cast<int>(iw.index); }
    };

    // finds all occurrence of a word in the list
    // given on construction
    std::vector<indexed_word> find_all(const std::string& w)
    {
        // our indexed word list
        std::vector<indexed_word> iws;

        unsigned int i = 0;
        // iterate through every word in the class' vector
        for (const auto& word : words)
        {
            indexed_word iw(i, word);
            // if we find the word in the list
            // we put it in our indexed word list
            if (word == w)
            {
                iws.push_back(iw);
            }
            // increment the index
            i++;
        }

        return iws;
    }

    // helper function to find the minimal distance between an indexed word
    // and a list of indexed words
    // the indexed word vector contains the same words with different indexes
    int min_dist_in(const indexed_word& iw, std::vector<indexed_word>& iws)
    {
        int min = npos;

        // iterate through the given indexed word list
        for (const auto& iword : iws)
        {
            // if the distance is smaller
            // than the current min, change it
            if (std::abs(iw - iword) < min)
            {
                min = std::abs(iw - iword);
            }
        }

        return min;
    }

public:
    constexpr static int npos = std::numeric_limits<int>::max();

    MinimalDistance(const std::vector<std::string>& words) : words(words) {}
    int distance(const std::string& w1, const std::string& w2)
    {
        int min = npos;

        std::vector<indexed_word> iws1 = find_all(w1);
        std::vector<indexed_word> iws2 = find_all(w2);

        // if either of our vectors contain 0 elements,
        // return the 'not found min value'
        if (!(iws1.size() || iws2.size()))
            return min;

        // iterate through one of the word lists
        // the other will be the reference
        for (const auto& iw : iws1)
        {
            // finds a minimal distance between indexed words
            // in a given list
            const int n = this->min_dist_in(iw, iws2);
            // if this is smaller than the current minimum
            // change assign this value to it instead;
            if (n < min)
                min = n;
        }

        return min;
    }
};

int main()
{
    std::vector<std::string> words{ "the", "quick", "brown", "fox", "is", "coming", "quick", "to", "catch", "another", "quick", "fox" };

    MinimalDistance mindist(words);
    int dist = mindist.distance("quick", "fox");

    return 0;
}

I hope this'll help somewhat.
It uses lists of indexed words to find the minimal distance (absolute value) between them.

Edit:
Also I'm not too big of a C++ expert so any suggestions are welcome! Cheers!

Answer 4

Your code is not handling duplicate strings in the input array.

For eg, if the input array is ["ghi", "abc", "abc", "abc", "ghi", "def", "ghi", "def"] Then minimum distance between "abc" and "def" should be: 2(between index 3 and 5) but your code will output: 4