题解 | #反转字符串#

NC103 反转字符串

1. 倒过来加

思路比较简单，遍历字符串，把每个字符往前加就行了。

class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    string solve(string str) {
        string res;
        for (auto c:str) res = c+res;
        return res;
    }
};

• 时间复杂度：字符串的长度为n，时间复杂度为O(n)，因为遍历了一次。
• 空间复杂度：O(n). 定义了一个长度也为n的变量res。

2. 双指针就地翻转

如图所示，定义两个指针分别从头和尾遍历，每次交换str[i]和str[j]就可以了。

class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    string solve(string str) {
        int i = 0, j = str.size()-1;
        while (i<j) {
            swap(str[i++], str[j--]);
        } 
        return str;
    }
};

• 时间复杂度：字符串的长度为n，时间复杂度为O(n)，因为只遍历了半条字符串，因此常数是思路一的一半。
• 空间复杂度：O(1), 只用到了常数个变量。