JuniorCodeCommonNot answered yet
URLify: replace spaces with %20 in place
Replace every space in a character buffer with %20, editing the buffer in place. The buffer is pre-sized so the longer result fits (no reallocation); you are given the true length of the text within it.
Requirements:
- O(n) time, O(1) extra space.
// buf has capacity for the expanded result; trueLen is the text length
void urlify(char* buf, int trueLen) {
// your code here
}Write the implementation.
Two passes. First count the spaces to compute the final length. Then write from the back: copy each character to its final slot, and for each space write '0', '2', '%' (reverse order). Writing right-to-left means you never overwrite unprocessed input. O(n) time, O(1) extra space.
- ✗Writing front-to-back and overwriting characters not yet processed
- ✗Forgetting to use the pre-sized capacity and writing past the original length
- ✗Emitting the
%20characters in the wrong order during the reverse pass
- →Why does writing from the back avoid clobbering unread characters?
- →How would the solution differ if you could not modify the buffer in place?
Contents
Task
Replace spaces with %20 in place in a pre-grown buffer in O(n) time and O(1) space.
Solution
void urlify(char* buf, int trueLen) {
int spaces = 0;
for (int i = 0; i < trueLen; ++i)
if (buf[i] == ' ') ++spaces;
int write = trueLen + spaces * 2 - 1; // last result slot
for (int read = trueLen - 1; read >= 0; --read) {
if (buf[read] == ' ') { // write "%20" backwards
buf[write--] = '0';
buf[write--] = '2';
buf[write--] = '%';
} else {
buf[write--] = buf[read];
}
}
}Key points
- The first pass counts spaces and computes the final length.
- Writing from the back never overwrites characters not yet read.
%20is written in reverse (0,2,%) because we move right to left.
Contents
