字符串

344. 反转字符串（Easy）

首尾双指针交换值即可。

void reverseString(vector<char>& s)
{
    int l = 0, r = s.size() - 1;

    while (l < r)
        swap(s[l++], s[r--]);
}

541. 反转字符串 II（Easy）

模拟这个过程，计数每2k个对前k个进行翻转。最后对剩余部分判断。

string reverseStr(string s, int k)
{
    int cnt = 0;
    int l, r, len = (int) s.length();
    for (int i = 0; i < len; i++)
    {
        if (++cnt == 2 * k)
        {
            l = i - k * 2 + 1, r = i - k;

            while (l < r) swap(s[l++], s[r--]);

            cnt = 0;
        }
    }
    l = len - cnt;
    r = cnt > k ? len - (cnt - k) - 1: len - 1;

    while (l < r) swap(s[l++], s[r--]);

    return s;
}

还有一个更简便的方法，直接每次循环都迭代器加上2k（一个周期），这样只用判断当先迭代器加上k是否大于字符串长度，如果大于，则说明剩余长度小于k，翻转剩余全部。小于则说明剩余部分大于k，翻转其中长度为k的部分。

string reverseStr_compact(string s, int k)
{
    for (int i = 0; i < s.length(); i += 2 * k)
    {
        if (i + k > s.length())
            reverse(s.begin() + i, s.end());
        else
            reverse(s.begin() + i, s.begin() + i + k);
    }

    return s;
}

剑指 Offer 05. 替换空格（Easy）

常规

• 空间复杂度\(O(n)\)

额外创建一个字符串用于存放替换后的结果。

string replaceSpace(string s)
{
    string res;

    for (char c: s)
    {
        if (c != ' ')
            res.push_back(c);
        else
            res += "%20";
    }

    return res;
}

双指针

• 空间复杂度\(O(1)\)

先遍历一次字符串，统计空格的数量。然后扩大字符串，从后向前填充字符串。（前向后涉及移动字符，时间复杂度为\(O(n^2)\)。）

string replaceSpace(string s)
{
    int spaceCnt = 0;

    for (char c: s)
        if (c == ' ') spaceCnt++;
    
    // current指向旧字符串最后一个字符
    int cur = s.size() - 1;
    s.resize(s.size() + 2 * spaceCnt);
    // previous指向新字符串的尾部
    int pre = s.size() - 1;
    
    for (; prev < cur; cur--, pre--)
    {
        if (s[cur] != ' ')
            s[pre] = s[cur];
        else
        {
            s[pre--] = '0';
            s[pre--] = '2';
            s[pre] = '%';
        }
    }

    return s;
}

151. 反转字符串中的单词（Medium）

使用一个额外空间

倒序读取字符串，找出每个单词，添加到res中。

string reverseWords(string s)
{
    string res;

    int l = s.length() - 1, r = l;

    while (l >= 0)
    {
        while (l >= 0 && s[l] == ' ') l--;
        if (l < 0) break;
        r = l;
        while (r >= 0 && s[r] != ' ') r--;

        res += s.substr(r + 1, l - r);
        res += ' ';
        l = r;
    }

    res.erase(res.end() - 1);

    return res;
}

双指针

• 使用快慢指针删除多余的空格

• 反转字符串

• 反转单词

// 这里快慢指针的思路是：
// 删除所有的空格，然后在每个单词前补上一个空格（需要排除第一个单词）
void removeExtraSpace(string& s)
{
    int slow = 0;

    for (int fast = 0; fast < s.length(); fast++)
    {
        if (s[fast] == ' ' ) continue;
        
        // 如果不是第一个单词则补上空格
        if (slow != 0) s[slow++] = ' ';

        while (fast < s.length() && s[fast] != ' ')
            s[slow++] = s[fast++];
    }

    s.resize(slow);
}

string reverseWords(string s)
{
    removeExtraSpace(s);

    reverse(s.begin(), s.end());

    int slow = 0;
    for (int fast = 0; fast <= s.length(); fast++)
    {
        if (s[fast] != ' ' && fast != s.length()) continue;

        reverse(s.begin() + slow, s.begin() + fast);
        slow = fast + 1;
    }

    return s;
}

剑指 Offer 58 - II. 左旋转字符串（Easy）

双指针

暂存需要被移动到末尾的子字符串。然后移动全部字符串。最后覆写。

string reverseLeftWords(string s, int n)
{
    int pre = 0, cur = n;
    string tmp = s.substr(0, n);

    while(cur < s.length())
        s[pre++] = s[cur++];

    int i = 0;
    while(pre < s.length()) s[pre++] = tmp[i++];

    return s;
}

局部翻转+整体翻转

string reverseLeftWords2(string s, int n)
{
    reverse(s.begin(), s.begin() + n);
    reverse(s.begin() + n, s.end());
    reverse(s.begin(), s.end());

    return s;
}

28. 找出字符串中第一个匹配项的下标（Medium）

暴力模拟

• 时间复杂度：\(O(mn)\)

int strStr_brutal(string haystack, string needle)
{
    int len = needle.length();

    if (len > haystack.length()) return -1;

    for (int i = 0; i < haystack.length() - len + 1; i++)
    {
        if (haystack.substr(i, len) == needle)
            return i;
    }

    return -1;
}

KMP算法

• 时间复杂度：\(O(m+n)\)

int* getNext(const string& str)
{
    int* next = new int[str.length()];

    int pre = -1;
    next[0] = pre;

    for (int suf = 1; suf < str.length(); suf++)
    {
        while (pre >= 0 && str[suf] != str[pre + 1]) pre = next[pre];

        if (str[suf] == str[pre + 1]) pre++;

        next[suf] = pre;
    }

    return next;
}

int strStr_KMP(string haystack, string needle)
{
    int* next = getNext(needle);

    for (int i = 0, j = -1; i < haystack.length(); i++)
    {
        while (j >= 0 && haystack[i] != needle[j + 1])
            j = next[j];

        if (haystack[i] == needle[j + 1]) j++;

        if (j == needle.length() - 1)
            return i - needle.length() + 1;
    }

    return -1;
}

459. 重复的子字符串（Easy）

KMP

使用KMP算法，对字符串进行遍历。因为上一个子串和下一个子串相同的情况下，模式串指针pre和字符串指针cur会相距一个固定距离。所以最后判断开始到pre的距离能否被剩余距离整除就可以判断是否有重复子字符串了。

同时也需要排除pre指针退回到最开始-1的情况（如果是全减一的next数组的话）

bool repeatedSubstringPattern(string s)
{
    int pre = -1;
    int next[s.length()];
    next[0] = pre;
    for (int cur = 1; cur < s.length(); cur++)
    {
        while (pre >= 0 && s[pre + 1] != s[cur]) pre = next[pre];

        if (s[pre + 1] == s[cur]) pre++;

        next[cur] = pre;
    }

    cout << pre << endl;

    if ((pre + 1) % (s.length() - pre - 1) == 0 && pre != -1)
        return true;

    return false;
}

利用循环节

将两个 s 作为一个字符串，然后从第二个字符开始寻找 s。

find 函数返回的是找到的第一个字符串的起始位置。

如果 s 是重复字符串，则从第二个字符开始寻找，就破坏了第一个 s 的重复性，但是可以通过和第二个 s 的字符串构成新的 s。

因此返回的值应该是小于 s.size() 的。

s	ss	找到的 s
abcabc	abcabcabcabc	bcabcabcabc
abcd	abcdabcd	bcdabcd

bool repeatedSubstringPattern(string s) 
{
    return (s+s).find(s, 1) < s.size();
}