Изменение положения слов в строке без изменения порядка специальных символов в O (1) пробел - PullRequest
Новая
       27

Изменение положения слов в строке без изменения порядка специальных символов в O (1) пробел

0 голосов
/ 25 августа 2018

Во время ложного собеседования у меня возникает вопрос.Интервьюер сначала задает этот вопрос без каких-либо ограничений пространства.Затем он продолжил с ограниченным пространством версии.Быть на той же странице.В вопросе дана строка и класс контейнера, состоящие из разделителей.Это зависит от вас, чтобы выбрать подходящий класс контейнера и язык ответа.Я думаю, что пример ввода и вывода будет достаточно, чтобы понять, что на самом деле вопрос.

Ввод: 

"Reverse#Strings Without%Changing-Delimiters"

Вывод: 

"Delimiters#Changing Without%Strings-Reverse"

Обратите внимание, что: Положение "#", "%", "", "-" не изменено

Я нашел решение, приведенное ниже: 

string ChangeOrderWithoutSpecial(string s, unordered_set<char> delimiter)
{
    stack<string> words; // since last words outs first
    queue<char> limiter; // since first delimiter outs first
    string response =""; //return value
    int index=-1; // index of last delimiter visited
    int len=s.length();
    for (int i =0 ; i <len;i++)
    {
        if(delimiter.find(s[i]) != delimiter.end()) // i-th char is a delimiter character
        {
            string temp=s.substr(index+1,i-index-1);
            words.push(temp);
            char t =s.at(i);
            limiter.push(t);
            index=i;
        }
    // i realized that part after interview under assumption starting with word and no double delimiters ie, each word followed by one delimiter
    if(index!=s.length()-1)
    {
        string temp=s.substr(index+1,s.length()-index-1);//until the end;
        cout<<temp<<endl;
        words.push(temp);
    }
    while(!limiter.empty())
    {
        response+=words.top()+limiter.front();

        words.pop();
        limiter.pop();
    }
    response+=words.top();
    return response;  

}

Однако я не смог найти ao(1) космическое решение?Кто-нибудь знает как?Я также не мог выяснить, если есть несколько разделителей, которые также должны быть оценены.Спасибо, что потратили время даже на чтение.

Ответы [ 2 ]

0 голосов
/ 27 августа 2018

Вместо поворота строки ее также можно решить путем последовательного обращения строки.

  • Перевернуть всю строку. Это операция O(n). В вашем случае строка становится sretimileD-gnignahC%tuohtiW sgnirtS#esreveR.
  • Найдите все слова и переверните каждое из них . Это O(n) операция. Строка теперь равна Delimiters-Changing%Without Strings#Reverse.
  • Обратные разделители . Это O(n) операция. Вы получите желаемый результат: Delimiters#Changing Without%Strings-Reverse.

Каждая из этих операций может быть выполнена на месте, поэтому общая сложность памяти составляет O(1), а сложность времени - O(n).

Стоит отметить, что при таком подходе каждый символ будет посещаться 4 раза (сначала обратный поиск, поиск слов, обратное слово, обратный разделитель), поэтому (в общем случае) он должен быть быстрее, чем ответ Игоря Тандетника где символы в середине строки посещаются много раз. Однако в особом случае, когда каждое слово имеет одинаковую длину, решение Игоря будет быстрее, потому что первая операция поворота не существует.

Edit:

Обратные разделители можно выполнить в O(n) без дополнительной памяти аналогично стандартному реверсу. Просто перебирайте разделители вместо целого набора символов:

  1. Итерация вперед до достижения разделителя;
  2. Итерация в обратном направлении, пока вы не достигнете разделителя сзади;
  3. Замена текущих разделителей;
  4. Продолжайте процедуру, пока ваши итераторы не встретятся.

Вот процедура в C++, которая будет выполнять эту работу 

void reverseDelimiters(string& s, unordered_set<char>& delimiters)
{
    auto i = s.begin(); auto j = s.end() - 1; auto dend = delimiters.end();
    while (i < j) {
        while (i < j && delimiters.find(*i) == dend) i++;
        while (i < j && delimiters.find(*j) == dend) j--;
        if (i < j) swap(*i, *j), i++, j--;      
    }
}
0 голосов
/ 26 августа 2018

Найти первое слово и последнее слово.Поверните строку на length(last_word)-length(first_word): это поместит среднюю часть в правильное положение.В этом примере будет получено 

ersReverse#Strings Without%Changing-Delimit

Затем поверните первую и последнюю часть строки, пропуская середину, на length(first_word): 

Delimiters#Strings Without%Changing-Reverse

Повторите этот алгоритм дляподстрока между двумя крайними разделителями.

Операция «Повернуть на m» может быть выполнена в O(1) промежутке и O(n) времени, где n - длина вращаемой последовательности.

...