[TOC]
class Solution {
public:
void reverseString(vector<char>& s) {
// special case
if (s.empty()) return;
int left = 0;
int right = s.size() - 1;
while (left < right) {
swap(s[left], s[right]);
++left;
--right;
}
}
};class Solution {
public:
string reverseStr(string s, int k) {
// special case
if (s.empty()) return "";
int time = s.size() / (2 * k);
int offset = 0;
while (time--) {
int left = offset;
int right = left + k - 1;
while (left < right) {
swap(s[left], s[right]);
++left;
--right;
}
offset += (2 * k);
}
int surplus = s.size() % (2 * k);
if (surplus < k) {
int left = offset;
int right = left + surplus - 1;
while (left < right) {
swap(s[left], s[right]);
++left;
--right;
}
} else {
int left = offset;
int right = left + k - 1;
while (left < right) {
swap(s[left], s[right]);
++left;
--right;
}
}
return s;
}
};class Solution {
public:
string reverseStr(string s, int k) {
// special case
if (s.empty()) return "";
for (int i = 0; i < s.size(); i += 2 * k) {
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k);
} else {
reverse(s.begin() + i, s.end());
}
}
return s;
}
};class Solution {
public:
string replaceSpace(string s) {
// special case
if (s.empty()) return "";
string res;
for (auto ch : s) {
if (ch == ' ') res.append("%20");
else res.insert(res.size(), 1, ch);
}
return res;
}
};class Solution {
public:
string replaceSpace(string s) {
// special case
if (s.empty()) return "";
int countOfSpace = 0;
int oldSize = s.size();
for (auto ch : s) {
if (ch == ' ') ++countOfSpace;
}
if (countOfSpace == 0) return s;
int newSize = oldSize + 2 * countOfSpace;
s.resize(newSize);
for (int i = oldSize - 1, j = newSize - 1; i < j; --i, --j) {
if (s[i] == ' ') {
s[j] = '0';
s[--j] = '2';
s[--j] = '%';
} else {
s[j] = s[i];
}
}
return s;
}
};class Solution {
public:
string reverseWords(string s) {
// special case
if (s.empty()) return "";
string res;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] != ' ') {
string str;
while (i >= 0 && s[i] != ' ') {
str.push_back(s[i]);
--i;
}
reverse(str.begin(), str.end());
res.append(str);
res.push_back(' ');
}
}
if (res[res.size() - 1] == ' ') res.pop_back();
return res;
}
};class Solution {
public:
// 反转字符串s中左闭又闭的区间[start, end]
void reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
// 移除冗余空格：使用双指针（快慢指针法）O(n)的算法
void removeExtraSpaces(string& s) {
int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
// 去掉字符串前面的空格
while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
fastIndex++;
}
for (; fastIndex < s.size(); fastIndex++) {
// 去掉字符串中间部分的冗余空格
if (fastIndex - 1 > 0
&& s[fastIndex - 1] == s[fastIndex]
&& s[fastIndex] == ' ') {
continue;
} else {
s[slowIndex++] = s[fastIndex];
}
}
if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
s.resize(slowIndex - 1);
} else {
s.resize(slowIndex); // 重新设置字符串大小
}
}
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() - 1);
for(int i = 0; i < s.size(); i++) {
int j = i;
// 查找单词间的空格，翻转单词
while(j < s.size() && s[j] != ' ') j++;
reverse(s, i, j - 1);
i = j;
}
return s;
}
};class Solution {
public:
string reverseLeftWords(string s, int n) {
// special case
if (s.empty()) return "";
string leftStr = s.substr(0, n);
string rightStr = s.substr(n);
return rightStr + leftStr;
}
};class Solution {
public:
string reverseLeftWords(string s, int n) {
// special case
if (s.empty()) return "";
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};class Solution {
public:
int strStr(string haystack, string needle) {
// special case
if (needle.empty()) return 0;
else if (haystack.empty()) return -1;
for (int k = 0; k < haystack.size(); ++k) {
int i = k;
int j = 0;
int res = k;
while (haystack[i] == needle[j] && i < haystack.size() && j < needle.size()) {
if (j == needle.size() - 1) return res;
++i;
++j;
}
}
return -1;
}
};class Solution {
public:
bool repeatedSubstringPattern(string s) {
// special case
if (s.empty()) return true;
for (int i = 1; i * 2 <= s.size(); ++i) {
if (s.size() % i == 0) {
bool match = true;
for (int j = i; j != s.size(); ++j) {
if (s[j] != s[j - i]) {
match = false;
break;
}
}
if (match) return true;
}
}
return false;
}
};