About Lesson
Question
Write a method to replace all 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.
Explanation
The question is asking to write a method that will take a string, its true length, and replace spaces with ‘%20’ within the given length constraints.
Examples
Example 1:
- Input:
"Mr John Smith ", 13 - Output:
"Mr%2eJohn%2eSmith" - Explanation: returns
Mr%2eJohn%2eSmithreplacing all spaces with%20and also it includes only 13 characters from the input string.
Constraints
- N/A
Practice
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.
- Loop to count spaces. Allocate double the spaces. Loop again, move characters to the end. If space, replace with ‘%20’.
/**
* Given two strings, create a function to determine whether they are permutations of each other.
* @param {string} str1
* @param {number} trueLength
* @return {string}
*/
const urlify = (str1, trueLength) => {
};
// some Tests from here
const assert = require("assert");
// Test 1: Replace spaces in a string with '%20'
const test1Result = urlify('Mr John Smith ', 13);
assert.strictEqual(test1Result, 'Mr%20John%20Smith', 'Test 1 failed');
// Test 2: No spaces in the string, no modification expected
const test2Result = urlify('MrJohnSmith', 11);
assert.strictEqual(test2Result, 'MrJohnSmith', 'Test 2 failed');
// Test 3: Replace spaces with '%20' for a string with true length less than the actual length
const test3Result = urlify('Mr John Smith ', 10);
assert.strictEqual(test3Result, 'Mr%20John%20Sm', 'Test 3 failed');
console.log('All tests passed.');
Solution
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.
Urlify Solution
const urlify = (str1, trueLength) => {
// count the spaces till trueLength
let spaceCount = 0;
const SPACE = ' ';
let strArray = str1.split('');
for (let i = 0; i < trueLength; i++) {
const currentChar = strArray[i];
if (currentChar === SPACE) {
spaceCount++;
}
}
// calculate full length
let finalLength = trueLength + (spaceCount * 2);
if (trueLength < strArray.length) { strArray = strArray.splice(0, trueLength); }
// iterate from backwards and replace with %20 in place of ' '
for (let i = trueLength - 1; i > 0; i--) {
const currentChar = strArray[i];
if (currentChar === SPACE) {
strArray[finalLength - 1] = '0';
strArray[finalLength - 2] = '2';
strArray[finalLength - 3] = '%';
finalLength = finalLength - 3;
} else {
strArray[finalLength - 1] = currentChar;
finalLength--;
}
}
return strArray.join('');
};
Explanation
- Count Spaces: Iterate through the input string
str1up to thetrueLengthand count the number of spaces. - Calculate Final Length: Calculate the final length of the modified string by adding twice the count of spaces to the
trueLength. This is to accommodate for the extra two letters coming from%20compared to a space. - Trim Excess Characters: If the
trueLengthis less than the actual length of the stringstr1/strArrayprovided, trim the array to the correct length. - Replace Spaces: Iterate backward through the array, starting from the last character of the true string. Replace spaces with ‘%20’ in place, updating the array and the final length accordingly.
- Join and Return: Join the modified array into a string and return the result.
Time Complexity
O(n), wherenis the length of the input string (str1). The time complexity is determined by the loop iterating through the string and the backward loop for replacing spaces. Both have a linear relationship with the length of the input string.
Space Complexity
- O(n), where n is the length of the input string (
str1). The space complexity is primarily determined by the arraystrArray.