Moment For Technology

[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

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).

Search
About
mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.