字符串专题-LeetCode：剑指 Offer 58 - II. 左旋转字符串、LeetCode 459.重复的子字符串、 代码思路和注意点

一、剑指 Offer 58 - II. 左旋转字符串

思路：

1. 预留出n个字符空间s.resize(s.size()+n)，把前n个字符存在s的最后面，整体前移
2. 也可以直接开辟一个新的空间，先存后n个字符，再存前n个字符
3. 不开辟额外空间，通过局部反转+整体反转，达到左旋转的目的，实现如下：

• 局部反转：前n个反转ba；后s.size()-1-n个反转gfedc bagfedc
• 整体反转：cdefgba

void reverse(string& s, int start, int end)
{
    for(int i=start,j=end;i<j;i++,j--)
    {
        swap(s[i], s[j]);
    }
}
string reverseLeftWords(string s, int n) {
    //1、局部反转：前n个反转ba；后s.size()-1-n个反转gfedc  bagfedc
    reverse(s, 0, n-1);
    reverse(s, n, s.size()-1);
    reverse(s, 0, s.size()-1);
    return s;
}

二、LeetCode 459.重复的子字符串

思路：

1. 如果s可以由重复子串构成，那么s+s也可以由重复子串构成。
2. 假设s=a1+a2，a1和a2完全相同，那么s+s也可以由a1和a2组成，即s+s’=a1+a2+a1’+a2’，**a2+a1’**也组成s。

代码展示

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        //1. 拼接
        string t = s+s;

        //2. 去头尾 避免直接找前s和后s 而不是中间的s
        t.erase(t.begin());
        t.erase(t.size()-1);
        //3. 找中间s std::string::npos 默认-1  
        if(t.find(s)!=std::string::npos) return true;
        
        //2和3等价于  if(t.find(s,1)!=s.size()) return true;
        return false;
    }
};

注意点：

1. 在s+s中找s时，要去掉s+s的首尾字符，否则找的就是前面或者后面的s，而不是中间的s，这样就会失去意义。
2. string& erase(int pos, int n = npos); —————删除从Pos开始的n个字符，只有一个参数时，
3. std::string::npos 静态常量，默认值为-1，不存在的位置
4. 不能 if(t.find(s)!=t.size()) return true; 对于只有三个字符的情况无法剔除，例如aba这种情况无法剔除
5. 代码中的2和3步骤相当于if(t.find(s,1)!=s.size()) return true;。此时从索引的第二个位置开始查找，如果不是字符串的结束位置，说明找到中间的s