Поиск наименьшей подстроки, содержащей все символы в векторе Страница 1 из 1 - PullRequest
Новая
       24

Поиск наименьшей подстроки, содержащей все символы в векторе Страница 1 из 1

0 голосов
/ 04 июля 2018

Я столкнулся с этой проблемой в списке проблем с примерами интервью с разработчиком программного обеспечения и пытался ее решить. Я придумал версию, которая работает в большинстве случаев, но один из моих тестовых примеров не удался, и я не могу понять, что происходит не так.

Пройденный тест:

Ввод: ["A", "B", "C"], "ADOBECODEBANCDDD"

Ожидаемый результат: "BANC"

Вывод программы: "ADOBEC" 

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

using namespace std;

string getShortestUniqueSubstring( const vector<char>& arr, const string &str )
{
  int minsize = str.size() + 1;
  string minstr = "";

  if (str.size() >= arr.size())
  {
      for (int i = 0; i < str.size(); i++)
      {
          for (int j = i + 1; j <= str.size(); j++)
          {
                if (j - i >= arr.size())
                {
                    string sub = str.substr(i, j);
                    bool found = true;

                    for (int k = 0; k < arr.size(); k++)
                    {
                        if (sub.find(arr[k]) == string::npos)
                            found = false;
                    }

                    if (found == true && sub.size() < minsize)
                    {
                        if (minsize == arr.size())
                            return sub;

                        minsize = sub.size();
                        minstr = sub;
                        break;
                    }
                }
            }
        }
  }
  return minstr;
}

int main()
{
  string inputstr = "ADOBECODEBANCDDD";
  vector<char> arr = {'A', 'B', 'C'};

  cout << getShortestUniqueSubstring(arr, inputstr);

  return 0;
}

1 Ответ

0 голосов
/ 04 июля 2018

Как уже упоминалось в комментариях, убедитесь, что вы правильно позвонили str.substr(); вам нужно передать начальный индекс подстроки и ее длину , а не ее конечный индекс.

Так что вместо: 

string sub = str.substr(i, j);

Обязательно укажите длину: 

string sub = str.substr(i, j - i);
...