字符串翻转

问题描述：把前 m 个字符搬到尾部

暴力翻转

首先先将一个字符移到尾部，然后重复 m 次，时间复杂度 O(mn)，空间 O(1)

三次翻转

时间复杂度 O(N) 空间 O(1) 分割成两段分别翻转，然后再整体翻转

void reverse(string &s, int from, int to) {
    while(from < to) swap(s[from++], s[to--]);
}

void ReverseStr(string &s, int m) {
    int n = s.length();
    // m 可能大于 n
    m %= s.length();

    reverse(s, 0, m-1);
    reverse(s, m, n-1);
    reverse(s, 0, n-1);
}

151. Reverse Words in a String 单词原地反转

其实思路和字符串的字符翻转差不多，第一次整个字符串反转，每个词的顺序颠倒，然后再双指针扫描空格反转单个词，最后再反转最后一个词

坑：注意去除前中后空格时间复杂度：O(N) 空间复杂度：O(1)

void reverseWords(string &s) {
    //trimming spaces at start
    int i=0;
    while(i<s.length() && s[i]==' '){
        s.erase(s.begin()+i);
    }

    //trimming spaces from the end.
    int j=s.length()-1;
    while(j>=0 && s[j]==' '){
        s.erase(s.begin()+j);
        j--;
    }

	// CC: 字符串只含空格
    if (s == "") return;
	// 1. reverse whole str
    reverse(s, 0, s.length()-1);
    
	// 2. reverse word by word (two pointers)
    for(i=j=0;i<s.length()-1;++i) {
        if (s[i] == ' ') {
            reverse(s, j, i-1);
            j = i+1;
			// CC: remove spaces before continue
            while (s[i+1] == ' ') s.erase(s.begin()+i+1);
        }
    }
    reverse(s, j, s.length()-1);
}

void reverse(string &s, int from, int to) {
    while(from < to) swap(s[from++], s[to--]);
}

收获

字符串反转的高效操作，三次反转

796. Rotate String

给定字符串 a, b。问是否能够通过 a 字符串的左移得到 b 字符串

解法一：暴力子串拼接 0ms

b 可以通过 a 在某位置分割调转后得到

bool rotateString(string a, string b) {
    if (a.length() != b.length()) return false;
    if (a == b) return true;

    for(int i=0;i<a.size();++i) {
		// 减少不必要的分割
        if (a[i] != b[0]) continue;
        if (a.substr(i, a.size()-i)
			+a.substr(0, i) == b) return true;
    }

    return false;
}

解法二：找规律 4ms

b 一定会出现在两个 a 合并成的新字符串中

bool rotateString(string A, string B) {
    return A.size() == B.size() && (A + A).find(B) != string::npos;
}

收获

string::npos 其实就是 -1 表示没找到

#双指针 #字符串

正则匹配系列