时间戳

首页 > 解决方案 > 反转字符串中单词的位置而不改变 O(1) 空间限制中特殊字符的顺序

c++ - 反转字符串中单词的位置而不改变 O(1) 空间限制中特殊字符的顺序

问题描述

在模拟面试中，我提出了这个问题。面试官首先问这个问题，没有任何空间限制。然后他继续使用空间有限的版本。要在同一页面上。在问题中，给出了由分隔符组成的字符串和容器类。这取决于您决定合适的容器类和响应语言。我认为样本输入和输出足以理解真正的问题是什么。

输入：

"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) 空间解决方案？有谁知道怎么做？我也无法弄清楚是否有多个分隔符，这也适用。谢谢有人花时间阅读。

标签： c++arraysstringreverse

解决方案

找到第一个单词和最后一个单词。将字符串旋转length(last_word)-length(first_word): 这会将中间部分放在正确的位置。在示例中，这将产生

ersReverse#Strings Without%Changing-Delimit

然后旋转字符串的第一部分和最后一部分，跳过中间部分length(first_word)：

Delimiters#Strings Without%Changing-Reverse

对两个最外层分隔符之间的子字符串重复此算法。

“Rotate by m”操作可以在O(1)空间和O(n)时间上进行，其中n是被旋转序列的长度。

推荐阅读