To Offer a daily topic | 3, replacing Spaces

One, foreword

Hello everyone, this is the third article in a series called “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

• Leetcode’s key Offer topic
• Code cloud warehouse address

Second, the subject

Implement a function that replaces each space in the string S with “%20”.

Example 1:

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

Limitations:

0 <= the length of s <= 10000

Third, the idea of solving the problem

The easiest way to think about this is idea 1. This is also very efficient, but takes up extra space. If both of them are implemented in Java, there is not much difference in this case. Both of them need to use Stringbuilder to temporarily store the array, resulting in the waste of extra space, which requires O(n). However, if c ++ is used to implement the same logic, the space complexity can be reduced to O(1).

3.1 Idea 1: Traverse judgment

StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder: StringBuilder

If it is not empty, copy the value of string to builder, if it is empty, copy the value of %20 to Builder, so the logic is simple, but there is an extra O(n) space.

3.1.1 Code implementation

Java code implementation:

 private static String resolve(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)==' '){
                builder.append("%20");
            }else{
                builder.append(s.charAt(i));
            }
        }
        return builder.toString();
    }
Copy the code

3.1.2 Execution Effect

3.2 Idea 2: Slinky approach

This approach is to use a variety of mature language APi method to solve, know about it, the real use of the actual work is generally this, that is, known APi call engineers. Of course, the real use of this kind of words also from the essence of our brush algorithm.

3.2.1 code

Java code implementation:

Private static String resolve2(String s) {return s.place (" ","%20"); private static String resolve2(String s) {return s.place (" ","%20"); }Copy the code

3.2.2 Execution Effect

You can also see that actually the amount of memory that is consumed by calling the API is sometimes a little bit larger.

3.3 Idea 3: In situ solution

This solution is recommended in the book, but it is difficult.

1. First, we iterate through the string, counting the number of Spaces, and then calculating the length of the replaced string.

2. Copy and replace from the end of the string. First prepare two Pointers: p1 to the end of the original string and P2 to the end of the string.

3. Move p1 left step by step and copy the string it points to to the position indicated by P2.

4. When P1 encounters a space, as shown in Figure B, move P1 one space to the left, insert %20 into the three positions before P2, and move P2 forward 3 Spaces, as shown in Figure C.

5, continue to perform the previous steps, and then end.

3.3.1 Code implementation

There is no concept of Pointers in Java, but it is not impossible to implement them.

Java code implementation:

Int num=0; for (int i = 0; i < s.length(); i++) { if(s.charAt(i)==' '){ num++; StringBuilder builder = new StringBuilder(s); for (int i = 0; i < num*2; i++) { builder.append(" "); } int p1=s.length()-1; Int p2=builder.length()-1; // p2 pointer for (int I = s.length(); i >0 ; i--) { if(builder.charAt(p1)==' '){ builder.setCharAt(p2,'0'); builder.setCharAt(p2-1,'2'); builder.setCharAt(p2-2,'%'); p1--; p2=p2-3; }else{ builder.setCharAt(p2,builder.charAt(p1)); p1--; p2--; } } return builder.toString();Copy the code

3.3.2 Execution Effect

Four, summary

Java is a high performance resource, and strings are immutable. But idea 3 uses Java to restore the c++ pointer to this operation, which also improves performance.

This topic mainly investigates the string, and three ideas need to be mastered.

Ok, this is the end of today’s brush questions, welcome to like and comment exchange, sword finger Offer brush questions journey will continue to unfold!