 # [Do the problem is also a game] URL

Posted on Aug. 8, 2022, 6:28 p.m. by Sarah Barrett
Category: The back-end Tag: algorithm

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.

## 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 is`Final 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).

Search
Categories