A summary of string related problems from LeetCode with solutions in C++.
Problems:
344. Reverse String
541. Reverse String II
5. Replace Space
151. Reverse Words in a String
58. Reverse Left Words
28. Find the Index of the First Occurrence in a String
459. Repeated Substring Pattern
Problem: Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.
Case 1: Input: s = [“h”,”e”,”l”,”l”,”o”], Output: [“o”,”l”,”l”,”e”,”h”]
Case 2: Input: s = [“H”,”a”,”n”,”n”,”a”,”h”], Output: [“h”,”a”,”n”,”n”,”a”,”H”]
// C++
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size()-1; i < s.size()/2; i++, j--) {
swap(s[i], s[j]);
}
}
};
Problem: Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string. If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.
Case 1: Input: s = “abcdefg”, k = 2, Output: “bacdfeg”
Case 2: Input: s = “abcd”, k = 2, Output: “bacd”
// C++
class Solution {
public:
// [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]);
}
}
string reverseStr(string s, int k) {
// 1. Reverse first k characters in every 2k characters
// 2. Reverse first k characters in characters are between [k, 2k)
for (int i = 0; i < s.size(); i += (2*k)) {
if (i + k <= s.size()) {
// [start, end)
reverse(s, i, i + k - 1);
continue;
}
// 3. Reverse left characters that fewer than k characters
reverse(s, i, s.size()-1);
}
return s;
}
};
Problem: replace every space in string s with ‘%20’
Case 1: Input: s = “We are happy.”, k = 2, Output: “We%20are%20happy.”
// C++
class Solution {
public:
// Time complexity: O(n)
// Space complexity: O(1)
string replaceSpace(string s) {
// Get numbers of space
int count = 0;
int strOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// Resize string s with space replaced by '%20'
s.resize(s.size() + count*2);
int strNewSize = s.size();
// Replace space with '%20' from right to left
for (int i = strNewSize - 1, j = strOldSize - 1; j < i; j--, i--) {
if (s[j] != ' ') {
s[i] = s[j];
} else {
s[i] = '0';
s[i-1] = '2';
s[i-2] = '%';
i -= 2;
}
}
return s;
}
};
4. 151. Reverse Words in a String
Problem: Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Case 1: Input: s = “the sky is blue”, Output: “blue is sky the”
Case 2: Input: s = ” hello world “, Output: “world hello”
Case 3: Input: s = “a good example”, Output: “example good a”
// C++
class Solution {
public:
// [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]);
}
}
// Double pointer method
void removeExtraSpaces(string& s) {
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
// Remove all spaces
if (s[fast] != ' ') {
// If not first word, add ' ' in front of that word
if (slow != 0) {
s[slow] = ' ';
slow++;
}
while (fast < s.size() && s[fast] != ' ') {
s[slow] = s[fast];
slow++;
fast++;
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
// Remove extra space, only one space between each word
// no space before first word, or after last word
removeExtraSpaces(s);
// removeExtraSpaces() makes sure spaces are remove in front of first word
reverse(s, 0, s.size()-1);
int start = 0;
for (int i = 0; i <= s.size(); i++) {
// Reach end of word or end of string
if (i == s.size() || s[i] == ' ') {
// [start, end]
reverse(s, start, i - 1);
// Update pointer for next word
start = i + 1;
}
}
return s;
}
};
Problem: 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串“abcdefg”和数字2，该函数将返回左旋转两位得到的结果“cdefgab”。
Case 1: Input: s = “abcdefg”, k = 2, Output: “cdefgab”
Case 2: Input: s = “lrloseumgh”, k = 6, Output: “umghlrlose”
// C++
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
6. 28. Find the Index of the First Occurrence in a String
Problem: Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Case 1: Input: haystack = “sadbutsad”, needle = “sad”, Output: 0
Case 2: Input: haystack = “leetcode”, needle = “leeto”, Output: -1
// C++
class Solution {
public:
// 构造next数组其实就是计算模式串s, 前缀表的过程
// i: 后缀末尾
// j: 前缀末尾, 包括i之前这个子串的最长相等前后缀的长度
// next: 前缀表, 找最长相等前后缀, ex. aabaaf: 0 1 0 1 2 0
void getNext(int* next, const string& s) {
// 初始化
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
// 处理前后缀不相同的情况
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 处理前后缀相同的情况
if (s[i] == s[j]) {
j++;
}
// 更新next数组的值
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}
};
7. 459. Repeated Substring Pattern
Problem: Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Case 1: Input: s = “abab”, Output: true
Case 2: Input: s = “aba”, Output: false
Case 3: Input: s = “abcabcabcabc”, Output: true
// C++
class Solution {
public:
void getNext (int* next, const string& s){
next[0] = 0;
int j = 0;
for(int i = 1;i < s.size(); i++){
while(j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if(s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern (string s) {
if (s.size() == 0) {
return false;
}
int next[s.size()];
getNext(next, s);
int len = s.size();
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
};