朋友给了一道大厂面试题，老梁一做发现不简单！

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

最近看到了一道某大厂的面试题，很有意思。

题面很简单，只有一句话，叫做翻转句子中的单词顺序，例如原本是：how are you翻转之后变成you are how。

老梁一看，这还不简单？如果使用Python只需要一行：

def revert_word(sentence):
    return ' '.join(sentence.split(' ')[::-1])

这么操作了之后被朋友告知不能使用split函数，需要自己处理空格。

老梁想了一下，这也不难，我们用一个字符串维护当前的单词，遇到空格就把它添加到答案的开头：

string revert_word(string &input) {
    string word = "", ret = "";
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == ' ') {
            ret = word + " " + ret;
            word = "";
            continue;
        }
        word = word + input[i];
    }
    return word + " " + ret;
}

但我们仔细想一下又会发现有一些问题，首先是这个word。我们每次读到新的字符之后都要拼接到末尾，这里其实有一个问题，在执行word = word + input[i]的时候，程序会先执行word + input[i]得到一个临时的字符串之后，再赋值给左侧的word，而不是在word本身进行修改。

我们都知道，复制是需要开销的，每次都是O(n)的操作。所以这样写的时间复杂度其实很大，接近O(n^2) 。

同样的问题还出现在更新ret的地方，所以表面上来看这个算法没问题，但仔细分析的话会发现它的复杂度是比我们预想的大的。

当我把我的分析告诉了朋友之后，他指出了另外一个问题，他说我们还用到了额外内存空间，面试官给的要求是除了时间复杂度控制在O(n) 之外，还需要将空间复杂度控制在O(1) 。

这就意味着我们不能再缓存单词，甚至不能存储拷贝，只能在原字符串上进行修改了。

老梁一开始的想法是维护两个指针分别指向头尾，拿到头尾的两个单词之后再进行交换。但这样有一个问题，就是当头尾的单词长度不一致的时候，没办法处理，如这种情况：

you xxxxx hello

我们要把hello和you两个单词交换位置，但交换之后会影响中间一系列字符的位置。显然在线性表当中移动元素是非常不明智的，自然这条路也就走不通了。

那有没有什么办法可以在O(n)的时间复杂度内做到这点呢？当然是有的，并且说白了很简单，甚至有点简单到出人意料，那就是翻转字符串。

你看原本是how are you的字符串在进行了翻转之后，会变成uoy era woh。不仅单词的顺序翻转了，并且每个单词当中的字母也翻转了。既然如此，那么我们只需要再将这些单词再翻转一遍即可。翻转单词显然是一个O(n) 的操作，并且也不需要额外的空间消耗。

除了算法本身，我们在写的时候还需要注意一下开发的规范，比如命名规范，传参的时候尽量传引用等等。

void swap_word(string &input, int l, int r) {
    while (l < r) {
        swap(input[l++], input[r--]);
    }
}

void revert_string(string &input) {
    reverse(input.begin(), input.end());
    int last = 0;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == ' ' && i > 0) {
            int l = last, r = i-1;
            swap_word(input, l, r);
            last = i+1;
        }
    }
    if (last < input.length()) {
        int l = last, r = input.length()-1;
        swap_word(input, l, r);
    }
}

这道题说难当然不算难，但说简单其实也没有那么简单，属于那种人人都能做，但未必都能想出最优解法的问题。非常能够考验一个工程师的功底，也的的确确配得上大厂面试题的称号。

后来老梁搜了一下，发现这题是剑指offer中的第58题，LeetCode中也有收录，感兴趣的小伙伴不妨亲自做做看~

新年在即，大家好好努力~