URLify a given string

URLify a given string

Write a method to replace all the spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end to hold the additional characters and that you are given the “true” length of the string.

Solutions

A common approach in string manipulation problems is to edit the string starting from the end and working backwards. This is useful because we have an extra buffer at the end, which allows us to change characters without worrying about what we're overwriting.

Approach 1 – Using string replace method

---

Steps

1. First check if string is null. if string is null, then return string.

2. Trim string from both sides.

3. Use string replace method to replace empty space with %20.

    public string URLify(string str)
    {
        if (str is null)
            return str;
        str= str.Trim();

        return str.Replace(" ", "%20");

    }

Time Complexity: O(n)

Auxiliary Space: O(1)

Approach 2 – Using two-scan approach.

---

Steps

1. First check if string is null. if string is null, then return string.

2. Trim string from both sides.

3. Now, count total number of spaces.

4. create new array of characters with new length (length +spaces*2). Here, takes length after trim.

5. Run loop for each characters of string and add it into new array.

    public string URLify(string str)
    {
        if (str is null)
            return str;

        int startIndex = 0;
        int endIndex = str.Length - 1;
        while (str[startIndex] == ' ')
        {
            startIndex++;
        }

        while (str[endIndex] == ' ')
        {
            endIndex--;
        }

        var spaceCount = 0;
        int i = startIndex;
        while (i <= endIndex)
        {
            if (str[i] == ' ')
            {
                spaceCount++;
            }
            i++;
        }

        if (spaceCount == 0)
        {
            return str;
        }

        int length = (endIndex - startIndex) + spaceCount * 2 + 1;
        var output = new char[length];
        int index = length - 1;
        for (i = endIndex; i >= startIndex; i--)
        {
            if (str[i] == ' ')
            {
                output[index] = '0';
                output[index - 1] = '2';
                output[index - 2] = '%';
                index -= 3;
            }
            else
            {
                output[index--] = str[i];

            }
        }
        return new string(output);
    }

Time Complexity: O(n)

Auxiliary Space: O(1)