⭐ Introduction ⭐ ️
Hello, everyone. I'm an executive. Today we bring you a set of special training on string processing. No matter you are studying or working, you must have a lot of contact with string. If you deal with string at ordinary times, you must use library functions directly. After all, there are many library functions for strings. As long as you can think of operations in languages such as Java and Python, they are basically encapsulated for you. However, it is easy for people to form a bad habit. They only use library functions and have a weak foundation. Therefore, when laying the foundation, don't be infatuated with library functions!! In order to help my brothers lay a better foundation, I sorted out this special training on string processing, from easy to difficult, to help you perfect the transition and consolidate the foundation, with detailed analysis. It is suggested that brothers collect and train when they are free.
⭐ Wonderful playback ⭐ ️
⭐ Knowledge navigation ⭐️
🍅 1. Mobilization instructions
🍐 2. Processing characters, bloody force deduction
🍐 4. Flip the words in the string (medium)
🌽 7. The first unique character in the string
🍋 3. Summary of basic string processing (Title General link)
🍅 1. Mobilization instructions
This chapter aims to exercise the basis of string processing for everyone. While doing questions, you should also know whether your language contains corresponding library functions. In advanced training problems, you should directly use library functions, otherwise the code will be very redundant. Because the processing of advanced problem strings is often only part of the problem, while basic training only needs to process strings. So when you train, you must also remember whether there is an appropriate library function.
🍐 2. Processing characters, bloody force deduction
🍍 1. Reverse string
Write a function that inverts the input string. The input string is given as a character array s.
Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.
Title Link: Reverse string
Topic analysis: the requirement of the topic is very simple, that is, inverting the character array, but it requires operation on the original array, so we can't exchange it with a new char [] array. In that case, we must think of using double pointers, one pointing to the head of the array and the other pointing to the tail of the array. After exchanging values, move inward at the same time and continue until the two pointers meet.
Method: double pointer
Time complexity O(n): n is the length of array s, which has been exchanged N/2 times, constant 1 / 2 is rounded off, and time complexity is O(n)
Spatial complexity O(1): only two int variables are used, and the complexity is O(1)
class Solution {
public void reverseString(char[] s) {
//The left pointer points to the head and the right pointer points to the tail
int left=0;
int right=s.length-1;
while(left<right){
//Exchange value
exch(left,right,s);
//The two pointers move to the middle at the same time
left++;
right--;
}
}
//Write an exchange method
public void exch(int i,int j,char[] s){
char a=s[i];
s[i]=s[j];
s[j]=a;
}
}🍠 2. Reverse string||
Given a string s and an integer k, the first k characters in the 2k characters are reversed for every 2k characters counted from the beginning of the string.
If there are less than k remaining characters, all remaining characters are reversed.
If the remaining characters are less than 2k but greater than or equal to K, the first k characters are reversed and the remaining characters remain as they are.
Title Link: Reverse string||
Problem analysis: this problem is the advanced level of the first problem. The difficulty is to know the appropriate reversal range. We use pointer l and pointer r to find the range to be reversed each time. In particular, note that in the end, R is directly + k-1 on the basis of l, which may exceed the length of the array, so you need to take a small value between R and n-1 every time. It is suggested to draw a picture to understand the subscripts of l and R. don't rely on your brain alone. This is a big taboo.
Method: double pointer
Time complexity O(n): n is the length of s.
Spatial complexity O(1) or O(n): it depends on your language. For example, String in Java is immutable. We can only use a char array for modification. If your language String can be modified, you can operate in the original array. At this time, the time complexity is O(1).
class Solution {
public String reverseStr(String s, int k) {
char[] arr=s.toCharArray();
int n=arr.length;
//l pointer + 2k each time
for(int l=0;l<n;l=l+2*k){
//r + k-1 on the basis of l every time (because the subscript is found, it is recommended to draw a graph and write the subscript to understand it)
int r=l+k-1;
//If r exceeds the length of the array, then r is larger than n-1. We can only get n-1
reverse(arr,l,Math.min(n-1,r));
}
return String.valueOf(arr);
}
//Write an inversion method to reverse the index interval specified by char [] array
public void reverse(char[] arr,int i,int j){
while(i<j){
char a=arr[i];
arr[i++]=arr[j];
arr[j--]=a;
}
}
}🍌 3. Replace spaces
Please implement a function to replace each space in the string "{s}" with "% 20".
Title Link: Replace spaceshttps://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/Replace spaces
Topic analysis: because it is a String, the String of some languages can be modified, and the String of some languages can not be modified. For example, the String of Java can not be modified. So here we use StringBuilder. Of course, StringBuffer can also be used. Both are modifiable String classes, but StringBuilder is more efficient. We traverse the String given by the title. If it is not a space, add the same after StringBuilder. If it is a space, add% 20. Finally, convert StringBuilder into String and return.
Method: use variable string (string array can also be used here) to traverse and add
Time complexity O(n): n is the length of the string, mainly the traversal time
Spatial complexity O(n): the StringBuilder object is mainly created, and the longest length may be 3n.
class Solution {
public String replaceSpace(String s) {
StringBuilder arr=new StringBuilder();
for(int i=0;i<s.length();i++){
//If it is a space, add% 20
if(s.charAt(i)==' '){
arr.append("%20");
}else{
//If it's not a space, add it to the end of arr
arr.append(s.charAt(i));
}
}
//Return String form
return arr.toString();
}
}🍐 4. Flip the words in the string (medium)
Give you a string s and flip all the words in the string one by one.
A word is a string of non whitespace characters. Use at least one space in s to separate words in the string.
Please return a string that flips the word order in s and connects it with a single space.
explain:
The input string s can contain extra spaces before, after, or between words.
After flipping, the words should be separated by only one space.
The flipped string should not contain additional spaces.
Title Link: Flip the words in the string
Problem analysis: this problem is a more difficult one in the string, because it examines almost all string processing operations. It is still difficult to complete it efficiently. Even with API, many people can't start, but it also allows us to solve more API operations. It is a very good problem. Now I'll explain a variety of methods and their efficiency.
❗ ⅶ analysis of test site: 1 How to trim off spaces at both ends
2. How to reverse words
3. How to skip consecutive spaces in the middle
Method 1: double pointer traversal inversion (key methods)
First, we convert the String of the question to char [], and a StringBuilder receives the answer. By traversing from the beginning to the end of the pointer, if the value of the pointer is a space, move to the middle until it is not a space, so the beginning and end spaces are cut off. Because you want to reverse the word, start looking for the word from the following right, move an index pointer to the left from the right position, find the position of space, stop, and then traverse the word at the inverted right position of index+1 into StringBuilder. Then, the index continues to move to find the position that is not a space, and then updates right. Then, the same operation is performed until the traversal of the array is completed. In fact, in addition to removing the head and tail blanks, left has not been moved in the whole process. Right is also updated by index, mainly the movement of index.
As it is difficult to express ideas in words alone, we have found a high-quality diagram for you. It is suggested to take a look at it carefully—— Double pointer diagram
Time complexity O(n): n is the length of s, which is traversed only once
Space complexity O(n): it is mainly used to store strings. Depending on the language, the language space complexity of variable strings can be O(1)
class Solution {
public String reverseWords(String s) {
//Convert to char array
char[] arr = s.toCharArray();
int left = 0;
int right = arr.length-1;
//Used to receive answers
StringBuilder sb = new StringBuilder();
//Remove spaces
while(arr[left]==' ') left++;
while(arr[right] == ' ') right--;
//Note the cycle end condition
while(left <= right){
//index starts with right
int index = right;
//Stop where it is empty. Note that it must also be greater than or equal to left, otherwise the array may cross the boundary when you go to the far left
while(index >= left && arr[index] != ' ' ) index--;
//Note that at this time, the index points to a space, and characters from inde+1 to right are added to StringBuilder
for(int i = index+1 ; i <= right ; i++ ) sb.append( arr[i] );
//Because a space needs to be added between the words in the middle, when index > left, it means that it is still in the middle. Let's fill in a space
if(index > left) sb.append(' ');
//Then we continue to move index to find the next word. At this time, we should also ensure that index > = left. The principle is the same as above
while( index >= left && arr[index]==' ' ) index--;
//Then update right to index
right = index;
}
return sb.toString();
}
}Method 2: API method (although the complexity is similar, the efficiency is lower than that of double pointers)
Time complexity: O(n), where nn is the length of the input string.
Spatial complexity: O(n)O(n), used to store the results after string segmentation
Above, we talked about the test site analysis of this question. If we can use APIs to complete these requirements, the code will be very simple. The premise is that we should be able to use and understand these APIs.
API of official solution:
class Solution {
public String reverseWords(String s) {
// Remove white space characters at the beginning and end
s = s.trim();
// Regular matching uses continuous white space characters as separators
List<String> wordList = Arrays.asList(s.split("\\s+"));
//The reverse method with Collections can be reversed, but a List needs to be passed in
Collections.reverse(wordList);
//String. The join method is very popular. It can insert the first parameter between two elements of the second parameter
return String.join(" ", wordList);
}
}API method I wrote:
class Solution {
public String reverseWords(String s) {
//Remove the API with leading and trailing spaces. You need to be able to use
String c=s.trim();
//Take continuous spaces as the delimiter, which involves regular expressions
//ps:split is widely used. Please be sure to learn it
String[] arr=c.split("\\s+");
StringBuilder a=new StringBuilder();
//from
for(int i=arr.length-1;i>=0;i--){
//Insert words from the tail to the head
//Fill in a space after each insertion
a.append(arr[i]+" ");
}
//There is no space after the last word. Delete the last word
a.deleteCharAt(a.length()-1);
return a.toString();
}
}🍑 5. Left rotation string
The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to realize the function of string left rotation operation. For example, if you enter the string "abcdefg" and the number 2, the function will return the result "cdefgab" obtained by rotating two bits left.
Title Link: Left rotation string
Topic analysis: the requirements of the topic are very simple, just move the first n characters to the back. We can use StringBuilder or StringBuffer to receive the next characters first, and then the first n characters.
Method 1: StringBuffer receive
Time complexity O(n): n is the length of s and the traversal time
Space complexity O(n): mainly the consumption of StringBuffer
PS: if only String is required in the interview, String can also be used here, but String in Python and Java is immutable. Each time, a new String must be created and the splicing efficiency is low. Memory must be applied every time. When the amount of data is large, the efficiency is low and the application memory is high.
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuffer a=new StringBuffer();
for(int i=n;i<s.length();i++){
a.append(s.charAt(i));
}
for(int i=0;i<n;i++){
a.append(s.charAt(i));
}
return a.toString();
}
}Method 2: substring of String (high efficiency, need to master, common API)
Time complexity O(n):n is the length of s
Space complexity O(n):n is the length of s
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
🍈 6. Length of the last word
I'll give you a string {s, which consists of several words separated by some space characters. Returns the length of the last word in a string.
The word {refers to the largest substring that consists of only letters and does not contain any space characters.
Title Link: Length of the last wordForce buckleLength of the last word
Analysis: this problem can be regarded as the sub problem of the fourth problem. We can consider the same approach. Reverse traversal uses the pointer to find the start index and end index of the last letter, so as to obtain the length.
Method: reverse traversal
Time complexity O(n): n is the length of the string, and the whole string can be traversed in reverse at most once
Space complexity O(1):
class Solution {
public int lengthOfLastWord(String s) {
//Traverse from the end
int index=s.length()-1;
//There are spaces at the end and move to the left
while(s.charAt(index)==' '){
index--;
}
//At this time, index points to the last letter of the last word, and a is used to record the position at this time
int a=index;
//Continue to move index to ensure that index > 0
//Note here that the index points to the space before the last word
while(index>=0&&s.charAt(index)!=' '){
index--;
}
//Subtract to get length
return a-index;
}
}🌽 7. The first unique character in the string
Given a string, find its first non repeating character and return its index. If it does not exist, - 1 is returned.
Title Link: The first unique character in the stringForce buckleThe first unique character in the string
Topic analysis: when you see this topic, you should first think of the indexOf and lastindexOf API methods of String, and then think of the brute force traversal method. For efficient methods, we should think of using hash. Here we do not use map but array mapping, because array is also an embodiment of hash mapping. what? You say you don't know much about hashing or array hashing? Then look at this hash project—— [hash series] my roommate was worried that I couldn't sleep in the final exam. I prepared this set of hash topics all night
Method 1: use indexOf and lastIndexOf of String
Time complexity O(n^2): it involves the API source code, and the internal implementation is also circular. This method has high complexity
Space complexity O(1)
class Solution {
public int firstUniqChar(String s) {
for(int i=0;i<s.length();i++){
//indexOf gets the position where an element first appears from scratch
//lastIndexOf gets the position of the first occurrence of an element from tail to head
//If equal, it means that the letter is one
if(s.indexOf(s.charAt(i))==s.lastIndexOf(s.charAt(i))){
return i;
}
}
//Return - 1 not found
return -1;
}
}Method 2: using array hash mapping
Time complexity O(n): perform traversal twice. Here you can also use hash table, but the efficiency of using array is better. It is recommended that you try both.
Space complexity O(1): array consumption of constant length, which is regarded as complexity consumption of O(1)
class Solution {
public int firstUniqChar(String s) {
//Count the frequency of 26 letters
int[] arr=new int[26];
//Traverse the array once and count the number of occurrences of each letter
for(int i=0;i<s.length();i++){
arr[s.charAt(i)-'a']++;
}
//Traverse again to find the letter with 1 occurrences
for(int i=0;i<s.length();i++){
if(arr[s.charAt(i)-'a']==1){
return i;
}
}
return -1;
}
}🍋 3. Summary of basic string processing (Title General link)
In fact, we found that almost every question about string can be answered directly or indirectly by API, which shows the importance of understanding string related API. However, in the process of using it, we should also master its principle. If you don't have this API, you can use it to realize this function. This is our basic skill. In the advanced problem, string processing is only part of it, and it will be combined with other algorithms. In order to simplify the code, we should use API to process it. Therefore, while laying a good foundation, we must also be able to use relevant APIs.
| 1. Reverse string | https://leetcode-cn.com/problems/reverse-string/ |
| 2. Reverse string ll | https://leetcode-cn.com/problems/reverse-string-ii/ |
| 3. Replace spaces | https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/ |
| 4. Reverse the words in the string | https://leetcode-cn.com/problems/reverse-words-in-a-string/ |
| 5. Left selection string | https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/ |
| 6. Length of the last word | https://leetcode-cn.com/problems/length-of-last-word/ |
| 7. The first unique character in the string | https://leetcode-cn.com/problems/first-unique-character-in-a-string/ |
Brothers who feel useful, look forward to supporting the third company!!! thank
Surprise at the end of the article:
Java learning route summary, brick movers counter attack Java Architects