String - Sword finger offer 05. replace spaces

1 Title Description

The finger of the sword Offer 05. Replace blank space

Please implement a function , Put the string s Replace each space in with "%20".

2 Title Example

Example 1：

Input ：s = “We are happy.”
Output ：“We%20are%20happy.”

3 Topic tips

0 <= s The length of <= 10000

4 Ideas

There are many solutions to this problem , Use many native apiapi It's easy to solve , for example ：

repleace/replaceAll
encodeURIComponent
split/join
Or directly break the solution and so on …

But we know , These are certainly not the purpose of being investigated , What we need to do , That is, how to implement it manually , Minimize complexity ！
It is worth noting that ： Array traversal , Be sure to traverse from back to front , Avoid front to back , Cause characters to be modified , Cause error ！

Because every replacement from 1 Characters become 3 Characters , Using character arrays makes it easy to replace . Set the length of the character array to s The length of the 3 times , This ensures that the character array can hold all the replaced characters .

• get s The length of 1ength
• Create a character array array, The length of 1ength * 3
• initialization size by 0,size Represents the length of the replaced string
• Traversing the string from left to right s
  • get s The current character of c
  • If the characters c Is a space , Then order array[size] = ‘%’,array[size + 1] = '2’, array[size + 2] ='0’, And will size The value of the add 3
  • If the characters C It's not a space , Then order array[size] = c, And will size The value of the add 1
• After the traversal ,size The value of is equal to the length of the replaced string , from array Before size Create a new string of characters , And return the new string

Complexity analysis

Time complexity ：O(n)O(n). Traversal string s Again .
Spatial complexity ：O(n)O(n). Create extra character arrays , The length is s The length of the 3 times .

5 My answer

class Solution {
    
    public String replaceSpace(String s) {
    
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
    
            char c = s.charAt(i);
            if (c == ' ') {
    
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
    
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}