URL-ификация строки

средне

# решено

Дан список s, представляющий URL-адрес (буквы и пробелы). Нужно заменить все пробелы в первых k символах на %20 in-place, используя свободное место в конце списка, и вернуть изменённый список s.

Пример 1:

Ввод: s = ["h","e","l","l","o"," ","w","o","r","l","d","#","#"], k = 11
Вывод: ["h","e","l","l","o","%","2","0","w","o","r","l","d"]

Пример 2:

Ввод: s = ["a"," ","b"," "," ","c","#","#","#","#","#","#"], k = 6
Вывод: ["a","%","2","0","b","%","2","0","%","2","0","c"]

Ограничения:

len(s) >= 1
k <= len(s)
Количество символов # в конце списка равно удвоенному количеству пробелов в первых k символах

public class Solution
{
    public static List<char> Urlify(List<char> s, int k)
    {
        // Slow - куда ставим символ, fast - откуда берём
        int slow = s.Count - 1;
        int fast = k - 1;

        while (fast >= 0)
        {
            if (s[fast] != ' ')
            {
                s[slow] = s[fast];
                slow--;
            }
            else
            {
                // Заменяем пробел на %20
                s[slow - 2] = '%';
                s[slow - 1] = '2';
                s[slow] = '0';
                slow -= 3;
            }
            fast--;
        }

        return s;
    }
}

#include <vector>
#include <string>

using namespace std;

vector<char> urlify(vector<char>& s, int k) {
    // slow - куда ставим символ, fast - откуда берём
    int slow = s.size() - 1;
    int fast = k - 1;

    while (fast >= 0) {
        if (s[fast] != ' ') {
            s[slow] = s[fast];
            slow--;
        } else {
            // заменяем пробел на %20
            s[slow - 2] = '%';
            s[slow - 1] = '2';
            s[slow] = '0';
            slow -= 3;
        }
        fast--;
    }
    return s;
}

package main

func urlify(s []rune, k int) []rune {
    // slow - куда ставим символ, fast - откуда берём
    slow := len(s) - 1
    fast := k - 1

    for fast >= 0 {
        if s[fast] != ' ' {
            s[slow] = s[fast]
            slow--
        } else {
            // заменяем пробел на %20
            s[slow-2] = '%'
            s[slow-1] = '2'
            s[slow] = '0'
            slow -= 3
        }
        fast--
    }
    return s
}

import java.util.*;

public class Solution {
    public List<Character> urlify(List<Character> s, int k) {
        // slow - куда ставим символ, fast - откуда берём
        int slow = s.size() - 1;
        int fast = k - 1;

        while (fast >= 0) {
            if (s.get(fast) != ' ') {
                s.set(slow, s.get(fast));
                slow--;
            } else {
                // заменяем пробел на %20
                s.set(slow - 2, '%');
                s.set(slow - 1, '2');
                s.set(slow, '0');
                slow -= 3;
            }
            fast--;
        }
        return s;
    }
}

from typing import *

def urlify(s: List[str], k: int) -> List[str]:
    # slow - куда ставим символ, fast - откуда берём
    slow = len(s) - 1
    fast = k - 1

    while fast >= 0:
        if s[fast] != " ":
            s[slow] = s[fast]
            slow -= 1
        else:
            # заменяем пробел на %20
            s[slow - 2] = "%"
            s[slow - 1] = "2"
            s[slow] = "0"
            slow -= 3
        fast -= 1
    return s

/**
 * @param {string[]} s
 * @param {number} k
 * @returns {string[]}
 */
export function urlify(s, k) {
  // slow - куда ставим символ, fast - откуда берём
  let slow = s.length - 1;
  let fast = k - 1;

  while (fast >= 0) {
    if (s[fast] !== " ") {
      s[slow] = s[fast];
      slow--;
    } else {
      // заменяем пробел на %20
      s[slow - 2] = "%";
      s[slow - 1] = "2";
      s[slow] = "0";
      slow -= 3;
    }
    fast--;
  }
  return s;
}

Оценка сложности

Время: O(n), где n - длина списка s
Память: O(1)

Частая ошибка оценивать время как O(k). Указатель fast действительно пробегает только k элементов, но slow пробегает все n элементов, поэтому и оценка O(n).