Title address

Interview question 01.03. Urlization

Topic describes

The URL. Write a method to replace all Spaces in a string with %20. Assume that there is enough space at the end of the string for new characters and that you know the “real” length of the string. (Note: If implemented in Java, use character arrays to operate directly on arrays.)

Example 1:

Input: "Mr John Smith", 13 output: "Mr%20John%20Smith"Copy the code

Example 2:

Input: "", 5 output: "%20%20%20%20%20"Copy the code

Tip:

• The value is in the range of 0, 500000.

Answer key

1. Build an array three times the length

• Construct an array three times the original length
• Iterate through the string, converting to 20% if you encounter a space
• The final position needs to be recorded because the length of the replaced string is not necessarily the length of the original string

The code is as follows:

class Solution {
    public String replaceSpaces(String S, int length) {
        if (S == null || S.length() == 0) {
            return S;
        }
        if (length == 0) {
            return "";
        }
        char[] charArray = S.toCharArray();
        
        char[] targetArray = new char[length * 3];
        int j = 0;
        for (int i = 0; i < length; i++) {
            char c = charArray[i];
            if (c == ' ') {
                targetArray[j++] = The '%';
                targetArray[j++] = '2';
                targetArray[j++] = '0';
            } else{ targetArray[j++] = c; }}return new String(targetArray, 0, j); }}Copy the code

Time is order n.

The space is O(3 times n).

2. Iterate over the original string to determine the final length

• The string is iterated over, counting the number of Spaces
• The length of the final string isFinal length = Original length + 2 x number of Spaces

The code is as follows:

class Solution {
    public String replaceSpaces(String S, int length) {
        if (S == null || S.length() == 0) {
            return S;
        }
        if (length == 0) {
            return "";
        }
        char[] charArray = S.toCharArray();
        int whiteSpaceCount = 0;
        for (int i = 0; i < length; i++) {
            char c = charArray[i];
            if (c == ' ') { whiteSpaceCount++; }}int targetLength = whiteSpaceCount * 2 + length;
        char[] targetArray = new char[targetLength];
        int j = 0;
        for (int i = 0; i < length; i++) {
            char c = charArray[i];
            if (c == ' ') {
                targetArray[j++] = The '%';
                targetArray[j++] = '2';
                targetArray[j++] = '0';
            } else{ targetArray[j++] = c; }}return newString(targetArray); }}Copy the code

Time is order n.

The space is O(n + 2 * m).