Article directory
- (Simple) 344. Reverse a string
- (simple) 541. Reverse a string||
- (Simple) Pointing to Offer 05. Replace spaces
- (Moderate) 151. Reverse words in a string
- (Easy) Pointing to Offer 58 – II. Left Rotating Strings
- (*Medium – KMP Algorithm) 28. Find the subscript of the first occurrence in a string
- (*simple – KMP algorithm) 459. Repeated substrings
(simple) 344. Reverse a string
class Solution {<!-- -->
public void reverseString(char[] s) {<!-- -->
int left = 0;
int right = s.length - 1;
while (left < right) {<!-- -->
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left ++ ;
right--;
}
}
}
Complexity analysis:
- Time complexity: O(N), where N is the length of the character array. A total of N/2 exchanges were performed
- Space complexity: O(1), only constant space is used to store several variables
(Simple) 541. Reverse String||
My idea: 2k characters as a group, first add the first k characters (or less than k characters) to StringBuilder, then call the reverse() method, and then add the last k characters (or less than 2k characters) Add to StringBuilder and finally add this group as a whole to the answer
class Solution {<!-- -->
public String reverseStr(String s, int k) {<!-- -->
int n = s. length();
int i = 0;
StringBuilder stringBuilder = new StringBuilder();
while (i < n) {<!-- -->
StringBuilder strk = new StringBuilder();
while (i < n & amp; & amp; strk. length() < k) {<!-- -->
strk.append(s.charAt(i));
i + + ;
}
strk. reverse();
while (i < n & amp; & amp; strk. length() >= k & amp; & amp; strk. length() < 2 * k) {<!-- -->
strk.append(s.charAt(i));
i + + ;
}
stringBuilder.append(strk);
}
return stringBuilder.toString();
}
}
My other idea: convert the string s into a character array, and then find a suitable interval in the character array for exchange
import java.util.regex.Pattern;
class Solution {<!-- -->
public String reverseStr(String s, int k) {<!-- -->
int n = s. length();
char[] charArray = s.toCharArray();
boolean flag = true;
int i = 0;
while (i < n) {<!-- -->
if (flag) {<!-- -->
int left = i;
int right = i + k > n ? n - 1 : i + k - 1;
while (left < right) {<!-- -->
char tmp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = tmp;
left ++ ;
right--;
}
i = i + k;
flag = false;
} else {<!-- -->
if (i + k >= n) {<!-- -->
break;
} else {<!-- -->
i + = k;
flag = true;
}
}
}
return new String(charArray);
}
}
Other ways of writing
It is also a simulation, reversing substrings of length k starting with each subscript starting at a multiple of 2k. If the length of the substring is less than k, reverse the entire substring.
class Solution {<!-- -->
public String reverseStr(String s, int k) {<!-- -->
int n = s. length();
char[] charArray = s.toCharArray();
for (int i = 0; i < n; i + = 2 * k) {<!-- -->
reverse(charArray, i, Math. min(i + k, n) - 1);
}
return new String(charArray);
}
public void reverse(char[] arr, int left, int right) {<!-- -->
while (left < right) {<!-- -->
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ++ ;
right--;
}
}
}
Complexity analysis:
- Time complexity: O(n), where n is the length of string s
- Space complexity: O(1) and O(n), depending on the nature of the string type in the language used. If the string is modifiable, it can be modified directly on the original string, and the space complexity is O(1), otherwise O(n) space is needed to temporarily convert the string into a modifiable data structure (such as an array) , the space complexity is O(n).
(simple) sword refers to Offer 05. Replace spaces
Method 1
class Solution {<!-- -->
public String replaceSpace(String s) {<!-- -->
return s.replaceAll(" ", " ");
}
}
Method 2
class Solution {<!-- -->
public String replaceSpace(String s) {<!-- -->
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < s. length(); i ++ ) {<!-- -->
char c = s.charAt(i);
if (c == ' ') {<!-- -->
stringBuilder. append(" ");
} else {<!-- -->
stringBuilder.append(c);
}
}
return stringBuilder.toString();
}
}
Other ideas
Since each replacement changes from 1 character to 3 characters, it is convenient to use a character array for replacement. The length of the established character array is 3 times the length of s, which ensures that the character array can accommodate all replaced characters.
class Solution {<!-- -->
public String replaceSpace(String s) {<!-- -->
int n = s. length();
char[] array = new char[n * 3];
int index = 0;
for (int i = 0; i < n; i ++ ) {<!-- -->
char c = s.charAt(i);
if (c == ' ') {<!-- -->
array[index + + ] = '%';
array[index + + ] = '2';
array[index + + ] = '0';
} else {<!-- -->
array[index + +] = c;
}
}
return new String(array, 0, index);
}
}
(moderate) 151. Reverse words in a string
class Solution {<!-- -->
public String reverseWords(String s) {<!-- -->
//Use trim() to remove the spaces at the beginning and end, and use split() to split according to " "
String[] splits = s.trim().split(" ");
StringBuilder stringBuilder = new StringBuilder();
for (int i = splits. length - 1; i >= 0; i--) {<!-- -->
//But there will be multiple spaces between words, skip directly when encountering splits[i].length==0
if (splits[i]. length() == 0) {<!-- -->
continue;
}
stringBuilder.append(splits[i]);
if (i != 0) {<!-- -->
stringBuilder. append(" ");
}
}
return stringBuilder.toString();
}
}
Official idea, solution one: use language features
Many languages provide methods such as split, reverse, and join for strings, so the operation can be completed by calling the built-in API
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
class Solution {<!-- -->
public String reverseWords(String s) {<!-- -->
s = s. trim();
List<String> wordList = Arrays.asList(s.split("\s + "));
Collections. reverse(wordList);
return String. join(" ", wordList);
}
}
Complexity analysis:
- Time complexity: O(n), where n is the length of the input string
- Space complexity: O(n), used to store the results after string segmentation
Official idea, method 2: write the corresponding function by yourself
These functions are different in different programming languages. The main difference is that some languages have immutable strings (such as Python, Java), and some languages have variable strings (such as C++).
For languages with immutable strings, the strings must first be converted into other mutable data structures, and spaces need to be removed during the conversion.
For languages with variable strings, there is no need to open up additional space, and the strings are implemented directly on the string. In this case, reversing characters and stripping spaces can be done together.
class Solution {<!-- -->
public String reverseWords(String s) {<!-- -->
//Remove redundant characters at the beginning, end and middle
StringBuilder sb = trimSpace(s);
// reverse the entire string
reverse(sb, 0, sb. length() - 1);
//Separate by spaces, reverse each word
reverseEachWord(sb);
return sb.toString();
}
private void reverseEachWord(StringBuilder sb) {<!-- -->
int start = 0;
int end = 0;
int n = sb. length();
while (end < n) {<!-- -->
while (end < n & amp; & amp; sb.charAt(end) != ' ') {<!-- -->
end + + ;
}
reverse(sb, start, end - 1);
start = end + 1;
end + + ;
}
}
private void reverse(StringBuilder sb, int left, int right) {<!-- -->
while (left < right) {<!-- -->
char tmp = sb.charAt(left);
sb.setCharAt(left, sb.charAt(right));
sb. setCharAt(right, tmp);
left ++ ;
right--;
}
}
private StringBuilder trimSpace(String s) {<!-- -->
int left = 0;
int right = s. length() - 1;
while (left <= right) {<!-- -->
//Remove the blank string at the beginning of the string
while (left <= right & amp; & amp; s. charAt(left) == ' ') {<!-- -->
left ++ ;
}
//Remove the blank string at the end of the string
while (left <= right & amp; & amp; s.charAt(right) == ' ') {<!-- -->
right--;
}
StringBuilder stringBuilder = new StringBuilder();
while (left <= right) {<!-- -->
char c = s.charAt(left);
if (c != ' ') {<!-- -->
stringBuilder.append(c);
} else if (stringBuilder. charAt(stringBuilder. length() - 1) != ' ') {<!-- -->
stringBuilder.append(c);
}
left ++ ;
}
return stringBuilder;
}
return null;
}
}
Complexity analysis:
- Time complexity: O(n), where n is the length of the input string, because the string needs to be traversed completely
- Space complexity: Java and Python methods require O(n) space to store characters, while C++ methods only require O(1) additional space to store several variables
Official idea, method three: double-ended queue
Since the double-ended queue supports the method of inserting from the head of the queue, we can process words one by one along the string, then push the word into the head of the queue, and then convert the queue into a string
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {<!-- -->
public String reverseWords(String s) {<!-- -->
int n = s. length();
int left = 0;
int right = s. length() - 1;
//Remove the blank string at the beginning of the string
while (left <= right & amp; & amp; s. charAt(left) == ' ') {<!-- -->
+ + left;
}
//Remove the blank string at the end of the string
while (left <= right & amp; & amp; s.charAt(right) == ' ') {<!-- -->
--right;
}
Deque<String> deque = new ArrayDeque<>();
StringBuilder word = new StringBuilder();
while (left <= right) {<!-- -->
char c = s.charAt(left);
if (word.length() != 0 & amp; & amp; c == ' ') {<!-- -->
deque.offerFirst(word.toString());
word.setLength(0);
} else if (c != ' ') {<!-- -->
word.append(c);
}
+ + left;
}
deque.offerFirst(word.toString());
return String. join(" ", deque);
}
}
Complexity analysis:
- Time complexity: O(n), where n is the length of the input string
- Space complexity: O(n), the double-ended queue requires O(n) space to store words.
In fact, the double-ended queue and stack in this place mean the same thing.
(Simple) Pointer to Offer 58 – II. Rotate strings to the left
To put it simply, it is to cut the string into two parts, exchange the positions of the two parts, splice them into a new string and return
class Solution {<!-- -->
public String reverseLeftWords(String s, int n) {<!-- -->
int len = s. length();
char[] chars = new char[len];
int index = 0;
for (int i = n; i < len; i ++ ) {<!-- -->
chars[index + + ] = s.charAt(i);
}
for (int i = 0; i < n; i ++ ) {<!-- -->
chars[index + + ] = s.charAt(i);
}
return new String(chars);
}
}
class Solution {<!-- -->
public String reverseLeftWords(String s, int n) {<!-- -->
int len = s. length();
StringBuilder stringBuilder = new StringBuilder(len);
for (int i = n; i < len; i ++ ) {<!-- -->
stringBuilder.append(s.charAt(i));
}
for (int i = 0; i < n; i ++ ) {<!-- -->
stringBuilder.append(s.charAt(i));
}
return stringBuilder.toString();
}
}
(*Medium – KMP Algorithm) 28. Find the subscript of the first match in a string
The most traditional string matching problem, the first reaction in my mind is the KMP algorithm, but I don’t remember what the idea is, so I wrote the violent matching method
class Solution {<!-- -->
public int strStr(String haystack, String needle) {<!-- -->
int n = needle. length();
int h = haystack. length();
if (n > h) {<!-- -->
return -1;
}
int i = 0;
int j;
while (i < h) {<!-- -->
if (haystack.charAt(i) != needle.charAt(0)) {<!-- -->
i + + ;
} else {<!-- -->
int k = i + 1;
j = 1;
while (k < h & amp; & amp; k < i + n & amp; & amp; haystack.charAt(k) == needle.charAt(j)) {<!-- -->
k++;
j + + ;
}
if (k == i + n) {<!-- -->
return i;
} else {<!-- -->
i + + ;
}
}
}
return -1;
}
}
The brute force method is to match the string needle and all substrings of length m of the string haystack once.
In order to reduce unnecessary matching, every time we fail to match, we immediately stop the matching of the current substring and match the next substring. If the current string matches successfully, just return the starting position of the current substring. If all substrings fail to match, -1 is returned
class Solution {<!-- -->
public int strStr(String haystack, String needle) {<!-- -->
int m = needle.length();//short
int n = haystack.length();//long
for (int i = 0; i + m <= n; i ++ ) {<!-- -->
boolean flag = true;
for (int j = 0; j < m; j ++ ) {<!-- -->
if (haystack. charAt(i + j) != needle. charAt(j)) {<!-- -->
flag = false;
break;
}
}
if (flag) {<!-- -->
return i;
}
}
return -1;
}
}
Complexity analysis:
- Time complexity: O(nm), where n is the length of the string haystack, and m is the length of the string needle. In the worst case, the string needle needs to be matched once with all substrings of length m of the string haystack.
- Space complexity: O(1), only requires constant space to save several variables.
KMP algorithm
The time complexity of the brute force method is O(mn), while the time complexity of KMP is O(m + n), because it can extract effective information for multiplexing in the process of non-exact matching, so as to reduce the cost of repeated matching. consume
The brute force method matches strings. When different positions appear, the pointer of the original string is moved to the next position of the starting point, and the pointer of the matching string is moved to the starting position. Continue to try to match, and find that it does not match, the pointer of the original string will always move backwards until it can be matched with the matching string.
import java.util.Arrays;
class Solution {<!-- -->
public int strStr(String haystack, String needle) {<!-- -->
int haystackLength = haystack. length();
int needleLen = needle. length();
if(needleLen > haystackLength){<!-- -->
return -1;
}
char[] haystackArr = haystack. toCharArray();
char[] needleArr = needle.toCharArray();
int[] next = new int[needleLen];
getNext(next, needle. toCharArray());
int i = 0;
int j = 0;
while (i < haystackLength) {<!-- -->
if (haystackArr[i] != needleArr[j]) {<!-- -->
while (j != 0 & amp; & amp; haystackArr[i] != needleArr[j]) {<!-- -->
j = next[j - 1];
}
if (j == 0 & amp; & amp; haystackArr[i] != needleArr[j]) {<!-- -->
i + + ;
}
} else {<!-- -->
i + + ;
j + + ;
}
if (j == needleLen) {<!-- -->
return i - j;
}
}
return -1;
}
private void getNext(int[] next, char[] arr) {<!-- -->
int len = arr. length;
int j = 0;
int i = 1;
while (i < len) {<!-- -->
if (arr[i] == arr[j]) {<!-- -->
next[i] = j + 1;
i + + ;
j + + ;
} else {<!-- -->
while (j > 0 & amp; & amp; arr[i] != arr[j]) {<!-- -->
j = next[j - 1];
}
if (j == 0 & amp; & amp; arr[i] != arr[j]) {<!-- -->
next[i] = 0;
i + + ;
}
}
}
}
}
(*simple – KMP algorithm) 459. Repeated substring
Assuming that the original string S is formed by repeating the substring s N times, then S + S has the substring s repeated 2N times, then now there are S=Ns, S + S=2Ns, where N>=2. If the condition is true, the two s are destroyed by pinching the head and the tail, and there are at least 2(N-1)s in S + S, and because N>=2, the index in S + S is from [0, length-2] must appear more than once in
class Solution {<!-- -->
public boolean repeatedSubstringPattern(String s) {<!-- -->
return (s + s).substring(1, (s + s).length() - 1).contains(s);
}
}
