<Sprinting big factory algorithm brushing questions>String

Hits: 0

📒Blog homepage: Big plum who loves programming📒

🌞Column homepage: LeetCode brush questions🌞

🙏The blogger is in the learning stage, if you find any problems, please let me know, thank you very much🙏

💙 At the same time, thank you very much for your support 💙

🌈 Word of the day: When you meet the dawn, you are young and just right. Dress up the army and horses, and engrave the elegance! 🌈

💗Thanks: I am just standing on the shoulders of giants to organize this article, thank you for the big guys who are on the way! 💗

🌟Finally, I wish everyone a million points of progress every day! Welcome everyone to like 👍➕ Favorite ⭐️➕ Comment 💬 Support the blogger 🤞! 🌟

⭐️ ⭐️The last article – <Sprinting big factory algorithm brushing questions>Hash table ⭐️ ⭐️

Article directory

344. Reverse [String]

Topic description

Write a function that reverses the input string. The input string is given as a character array s.

Instead of allocating extra space for another array, you have to modify the input array in place, using O(1) extra space to solve this problem.

Example 1:

Example 2:

Thought analysis

double pointer methodreverse the array

Reference Code

void reverseString(vector<char>& s) {
    for(int i = 0,j=s.size()-1;i<j;i++,j--){
        swap(s[i],s[j]);
    }
}

541. Reverse String II

Topic description

Given a string s and an integer k, every 2k characters counted from the beginning of the string, reverse the first k characters of the 2k characters.

If the remaining characters are less than k, 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 are left as-is.

Example 1:

Input: s = "abcdefg" , k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd" , k = 2
Output: "bacd"

Thought analysis

  • Every 2k character length, reverse the first k characters ==> This also determines that the increment of each round of i is 2k
  • If less than 2k but greater than k, reverse the first k.
  • If the remainder is less than k, all are reversed.

Reference Code

string  reverseStr ( string s, int k)  {
     int i = 0 ;
     for (; i < s.size();i+= 2 *k){
         if (i+k<s.size()) { //if every The remaining characters > k, then the first k can be reversed
            reverse(s.begin()+i,s.begin()+i+k);
        } else { //If there are not enough k, reverse all the remaining ones
            reverse(s.begin()+i,s.end());
        }
    }
    return s; 
}

Point to Offer 05. Replace spaces

Topic description

Please implement a function that replaces each space in the string s with “%20”.

Example 1:

Input: s = "We are happy." 
Output: "We%20are%20happy."

Thought analysis

Method 1: Double pointer

Because C++’s string maintains a character array at the bottom. We know that the deletion and insertion of array elements sometimes cause all elements to move backward, which is very time-consuming. All we canCount the spaces in the string in advance, and then restore the space to the final required space for the string.
We use fast and slow pointers when processing,Convert the space to %20 from back to front, while placing the element in the corresponding position. Finally return a string.

Algorithm steps:

  • Count the number of spaces in the string s: cnt
  • Reallocate larger space for s: s.size()+cnt*2
  • Define two pointers i, j from back to front, while converting the space to %20, while placing the element in the corresponding position
  • returns the string s

Method 2: String Concatenation

Define a string variable, if it is a non-space character, it will be spliced ​​directly, if it is a space, it will be spliced ​​with %20.Although it is the most common method, it is quite efficient, hehe

Reference Code

Method 1: Double pointer

#include<bits/stdc++.h>
using namespace std;

string replaceSpace(string s) {
    int j,k,cnt = 0;
    for(int i = 0;i < s.size();i++){
        if(s[i]==' '){
            cnt++;
        }
    }
    j = s.size()-1;
    k = s.size()+cnt* 2 -1 ;
     // Expand the capacity 
    s.resize(s.size()+cnt* 2 ) ;

    //traverse from back to front 
    while (j<k) {
         if (s[j]!= ' ' ){
            s[k] = s[j]; //If it is not a space, put the element at the specified position
            j--;
            k--;
        } else { //For spaces, replace spaces with %20 
            s[k] = '0' ;
            s[k-1] = '2';
            s[k-2] = '%';
            j--;
            k-=3;
        }
    }
    return s;
}

Method 2: String Concatenation

string replaceSpace(string s) {
    string ans="";
    for(int i = 0;i < s.size();i++){
        if(s[i]!=' '){
            ans+=s[i];
        }else{
            ans +="%20";
        }
    }
    return ans;
}

151. Flip words in a string

Topic description

Given a string s, 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 the words in the string.

Please return a string that reverses the order of the words in s and joins them with a single space.

illustrate:

The input string s can contain extra spaces before, after, or between words.
After flipping, words should be separated by only one space.
There should be no extra spaces in the flipped string.

Example 1:

Input: s = "the sky is blue" 
Output: "blue is sky the"

Example 2:

Input: s = "hello world" 
Output: "world hello"

Explanation: The input string can contain extra spaces before or after it, but the reversed characters cannot.

Example 3:

Input: s = "a good example" 
Output: "example good a"

Explanation: If there is an extra space between two words, reduce the space between the flipped words to only one.

Example 4:

Input: s = "Bob Loves Alice" 
Output: "Alice Loves Bob"

Example 5:

Thought analysis

Improve the difficulty of the problem: do not use auxiliary space, the space complexity requirement is O (1) O(1) O(1)

Problem solving ideas:

  • remove extra spaces
  • Reverse the entire string
  • reverse each word

For example, the source string is: “the sky is blue”

  • Remove extra spaces: “the sky is blue”
  • String reverse: “eulb si yks eht”
  • Word inversion: “blue is sky the”

So we’re done flipping the words in the string.

But how to remove spaces between words?

As a rookie, I think of loop + judgment + erase(), but you must know that the time complexity of erase() is also O(n), which leads to the overall time complexity of O(n^2);

Think about other ways we can reduce the time complexity, suddenly, in a flash, I thought of the previous chapter on arrays—removing the specified elements in the array, what we use isdouble pointer, to remove spaces, and that’s it!

Note: Since the built-in reverse cannot satisfy us to reverse the substring in the string, we need to customize the reverse method.

Reference Code

#include<bits/stdc++.h>
using namespace std;

//Remove spaces method 
void  removeExtraSpaces ( string & s)  {
     int slow = 0 ,fast = 0 ;

    //remove whitespace before string 
    while (fast<s.size() && s[fast]== ' ' ) { // a good example
        fast++;
    }

    //Remove spaces in the middle of the string 
    while (fast<s.size()) {
         if (fast>= 1 &&s[fast]== ' ' &&s[fast -1 ]== ' ' ) { //fast> =1
            fast++;
        } else {
            s[slow] = s[fast];
            slow++;
            fast++;
        }
    }

    //Remove the space after the string (if there is one, it must be one) 
    if (slow -1 >= 0 &&s[slow -1 ]== ' ' ) {
        s.resize(slow -1 ); //if the last character is a space 
    } else {
        s.resize(slow); //if the last character is not a space
    }
}

//Reverse the string time complexity O(N) 
void  reverse ( string & s, int i, int j)  {
     while (i<j) {
        swap(s[i],s[j]);
        i++;
        j--;
    }
}

string reverseWords(string s) {
    removeExtraSpaces(s); //remove spaces 
    reverse(s, 0 ,s.size() -1 ); //overall reverse 
    int i = 0 ,j;
     while (i<s.size()) { // reverse word
        j = i;
        while (j<s.size()&&s[j]!= ' ' ){ //Find the position j of the space
            j++;
        }
        reverse(s,i,j -1 ); //reverse word 
        i = j+ 1 ; //update i
    }
    return s; 
}

Sword Point Offer 58 – II. Rotate String Left

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 implement the function of left rotation of strings. For example, if you enter the string “abcdefg” and the number 2, the function will return the result “cdefgab”, which is left-rotated two places.

Topic description

Example 1:

Input: s = "abcdefg" , k = 2
Output: "cdefgab"

Example 2:

Input: s = "lrloseumgh" , k = 6
Output: "umghlrlose"

Thought analysis

method one

Directly intercept the string, and then splicing it together (no technical content)

Method Two

We become a big boss again, and the difficulty is increased: you cannot apply for extra space, you can only operate on this string

practice:Partial + Global Inversion

  • Invert the substring of the first n intervals
  • Reverse the substring in the range n to the end
  • reverse the entire string

Reference Code

#include<bits/stdc++.h>
using namespace std;

//Manually implemented reverse 
void  reverse ( string & s, int begin, int end)  {
     while (begin<end){
        swap(s[begin],s[end]) ;
        begin++;
        end--;
    }
}

//A reverse can be implemented manually 
string  reverseLeftWords ( string s, int n)  {
 // reverse(s.begin(),s.-()+n); 
// reverse(s.begin()+n,s .end()); 
// reverse(s.begin(),s.end()); 
    reverse(s, 0 ,n -1 ) ;
    reverse(s,n,s.size()-1) ;
    reverse(s,0,s.size()-1 ;
    return s;
}

28. Implement strStr()

Topic description

Implement the strStr() function.

Given two strings haystack and needle, please find the first position of the needle string in the haystack string (the subscript starts from 0). Returns -1 if not present.

illustrate:

What value should we return when needle is the empty string? This is a good question to ask in an interview.

For this problem, we should return 0 when needle is the empty string. This matches C’s strstr() and Java’s indexOf() definitions.

Example 1:

Input: haystack = "hello" , needle = "ll" 
Output: 2

Example 2:

Input: haystack = "aaaaa" , needle = "bba" 
Output: -1

Example 3:

Input: haystack = "" , needle = "" 
Output: 0

Thought analysis

Pure KMP algorithm, if you don’t understand, you can read my blog

Method to find the Next() array.

Reference Code

//haystack: text string needle: template string 
void  getNext ( int * Next, const  string & s)  {
     int i = 1 ,j = 0 ; //initialize i,j 
    Next[ 0 ] = 0 ;
     for (; i< s.size(); i++) {
         //find the same character 
        while (j> 0 &&s[i]!=s[j]) { //if s[i] and s[j] are not equal, then j goes back When the last common prefix position, until equal or j=0 (that is, can't go back further) 
            j = Next[j -1 ];
        }
        if (s[i]==s[j]) { //Determine whether the two characters after the back are equal
            j++;
        }
        Next[i] = j; //Update Next.
    }
}

//haystack: text string needle: template string 
int  strStr ( string haystack, string needle)  {

    int Next[needle.size()] ; //Define Next array 
    getNext(Next,needle); //Initialize 
    int j = 0 ,i = 0 ;
     for (; i<haystack.size(); i++) {
         // If not equal, the template string is adjusted to the next position of the longest common prefix 
        while (j> 0 &&haystack[i]!=needle[j]) {
            j = Next[j-1] ;
        }

        if(haystack[i]==needle[j]) {
            j++;
        }
        if (j==needle.size()) { //finish the search 
            return i-needle.size()+ 1 ; //return the starting index found.
        }
    }
    return  -1 ; // if not found, return -1 
}

459. Repeated Substrings

Topic description

Given a non-empty string, determine whether it can be formed by repeating one of its substrings multiple times. The given string contains only lowercase English letters and the length does not exceed 10000.

Example 1:

Input: "abab"

output: True

Explanation: The substring “ab” can be repeated twice.

Example 2:

Input: "aba"

output: False

Example 3:

Input: "abcabcabcabc"

output: True

Explanation: The substring “abc” can be repeated four times. (Or the substring “abcabc” repeated twice.)

Thought analysis

Classic use of KMP algorithm plus a little trick
Assuming the length of the array is len, if len % (len – next[len – 1]) == 0 , then the string has repeated substrings.
Why?
The length of the array minus the length of the longest identical prefix and suffix is ​​equivalent to the length of the first cycle, that is, the length of one cycle. If this cycle is divisible, it means that the entire array is a cycle of this cycle.
It’s clear when we look at the Next array, as follows:

Analysis:In the first cycle next[x]=0, when out of the first cycle next[i]>0, so if the string can be composed of a certain substring, then len – next [len – 1] must be divisible by len.

Reference Code

#include<bits/stdc++.h>
using namespace std;

void  getNext ( int * Next, const  string & s) {
     int i = 1 ,j = 0 ; //Define and initialize 
    Next[ 0 ] = 0 ;
     for (;i<s.size();i++) {
         while ( j> 0 &&s[i]!=s[j]){ //If it is not equal, j will go backward as the last common prefix position until it is equal or j=0 (that is, it cannot continue to go backward) 
            j = Next[j -1 ];
        }
        //Determine whether it is equal 
        if (s[i]==s[j]) {
            j++;
        }
        //Update Next[i]
        Next[i] = j; 
    }

}

bool  repeatedSubstringPattern ( string s)  {
     //The main idea is: string length % (string length - longest common prefix) = 0, it means there is a repeated substring 
    int len ​​= s.size();
     int Next[ len]; //Define Next array
    getNext(Next,s) ;
    if(Next[len-1]&&len % (len - Next[len-1])==0){
        return true;
    }
    return  false ;
}

int main(){
    string str = "abababaaba";
    cout<<repeatedSubstringPattern(str)<<endl;
    return 0;
}

Summarize

OK, that’s all for the sorting of string algorithms today , I hope this article can help you, and I hope you can learn something after reading it! ! !

Alright, see you next time~

You may also like...

Leave a Reply

Your email address will not be published.