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

Question

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

输入:

"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;  

} 

但是我找不到 o(1) 空间的解决方案？任何人都知道如何？我也不知道是否有多个定界符，也适用。感谢大家花时间阅读。

Answer 1

找到第一个词和最后一个词。将字符串旋转 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 是被旋转序列的长度。