97 lines
2.5 KiB
Markdown
97 lines
2.5 KiB
Markdown
# 1.3. URLify
|
|
|
|
## Replace all spaces in a string with '%20'. The string has sufficient space at the end to hold the additional characters, and as input we receive the true length of the string
|
|
|
|
> example:
|
|
|
|
* input: 'Mr John Smith ', 13
|
|
* output: 'Mr%20John%20Smith'
|
|
|
|
## First, understand the input
|
|
|
|
true length 13? so we're supposed to stop if we reach string length 13, even if the input string is longer? I assume this is the case.
|
|
|
|
## Initial idea
|
|
|
|
BCR is O(n), we have to go through the string at least once.
|
|
|
|
```python
|
|
def replace_char(s, maxlen):
|
|
news = ''
|
|
for i in range(maxlen):
|
|
if s[i] == ' ':
|
|
news += '%20'
|
|
else:
|
|
news += s[i]
|
|
return news
|
|
```
|
|
|
|
This runs in O(n) time and O(n) space. Can we do O(1) space? Replace in string directly?
|
|
|
|
`maxlen` must be smaller than `len`? If it's bigger, this won't work
|
|
|
|
```python
|
|
maxlen = min(maxlen, len(s))
|
|
```
|
|
|
|
At most, it'll be as long as `s`. What if it's negative?
|
|
|
|
```python
|
|
maxlen = max(0, maxlen)
|
|
```
|
|
|
|
> tests
|
|
|
|
* '', 3 -> ''
|
|
* 'ane ', 3 -> 'ane'
|
|
* 'ane ', 4 -> 'ane%20'
|
|
* 'a ne', 5 -> 'a%20ne'
|
|
|
|
## Improved idea
|
|
|
|
```python
|
|
def replace_char(s, maxlen):
|
|
maxlen = max(0, maxlen)
|
|
maxlen = min(maxlen, len(s))
|
|
for i in range(maxlen):
|
|
if s[i] == ' ':
|
|
s[i] = '%20' # fails
|
|
return s
|
|
```
|
|
|
|
don't know if this works in python... but it'd be O(1). Doesnt work in python, strings are inmutable. Either use lists, or:
|
|
|
|
```python
|
|
new = text[:1] + 'Z' + text[2:]
|
|
```
|
|
|
|
which creates another string, so O(n) anyway.
|
|
|
|
> REMEMBER: there's no append in strings in python, s += 'a'
|
|
|
|
Tests OK.
|
|
|
|
## Another language
|
|
|
|
Strings are mutable in C++:
|
|
|
|
```c++
|
|
int main() {
|
|
std::string s = "abc";
|
|
s[1] = 'a';
|
|
}
|
|
```
|
|
|
|
or use `string.replace()`. This'd take O(1) in space.
|
|
|
|
## Solution
|
|
|
|
A common approach is to edit the string starting from the end and working backwards, because we have an extra buffer at the end, which allows us to change characters without worrying about overwriting.
|
|
|
|
First count number of spaces (? why?). We need two extra characters for each space because `%20` is two characters longer than `' '`, so we multiply \# of spaces * 2. Then we walk backwards through the string, editing it. When we see a space, replace it with `%20`. Else, copy original character.
|
|
|
|
The solution is implemented in Java character arrays (`char[] str`), where strings are inmutable.
|
|
|
|
## Conclusion
|
|
|
|
Careful which language I use, strings might be mutable or not. Best case scenario, C++, O(n) time and O(1) space. |