1-3-URLify Algorithm
The 1-3-URLify Algorithm is a technique used to replace all spaces in a given string with the characters '%20', which is a common encoding for spaces when creating URL strings. This algorithm is essential in situations where we need to create a valid URL from a given string, such as when searching for a specific phrase or title on a website, and it ensures that the URL is properly formatted and easily interpreted by web browsers. The algorithm typically operates on a character array, rather than a string, to allow for efficient in-place manipulation. The input usually consists of a string with enough extra space at the end to accommodate the additional characters required for the '%20' replacements.
To implement the 1-3-URLify Algorithm, we can follow these steps: First, iterate through the string to count the number of spaces. With this count, we can calculate the new length of the string after the replacements. Then, starting from the end of the string, we work our way backwards, copying characters from their original position to their new position in the character array. If a space is encountered, we replace it with the characters '%20'. By working backwards, we ensure that we do not overwrite any characters that have not yet been processed. This method allows for efficient in-place manipulation of the character array, resulting in a URLified string without the need for additional data structures or memory allocation.
/*
* Cracking the coding interview Edition 6
* Problem 1.3 URLify --> Replace all the spaces in a string with '%20'.
* Assumption : We have enough space to accommodate addition chars
* Preferebly in place
*/
#include <iostream>
#include <cstring>
/*
* Function : urlify
* Args : string long enough to accommodate extra chars + true len
* Return : void (in place transformation of string)
*/
void urlify(char *str, int len)
{
int numOfSpaces = 0;
int i = 0, j = 0;
for ( i = 0; i < len; ++i ) {
if (str[i] == ' ') {
++numOfSpaces;
}
}
int extendedLen = len + 2 * numOfSpaces;
i = extendedLen - 1;
for( j = len - 1; j >= 0; --j ) {
if ( str[j] != ' ' ) {
str[i--] = str[j];
} else {
str[i--] = '0';
str[i--] = '2';
str[i--] = '%';
}
}
}
int main()
{
char str[] = "Mr John Smith "; //String with extended length ( true length + 2* spaces)
std::cout << "Actual string : " << str << std::endl;
urlify(str, 13); //Length of "Mr John Smith" = 13
std::cout << "URLified string : " << str << std::endl;
return 0;
}
