Problem
Write a C program that will replace all spaces with ‘%20′
Example
Input: “Mr John Smith "
Output: “Mr%20John%20Smith
Solution
The algorithm is as follows:
- Count the number of spaces during the first scan of the string.
- Parse the string again from the end and for each character:
If a space is encountered, store “%20”.
Else, store the character as it is in the newly shifted location.
Java code
public static void ReplaceFun(char\[\] str, int length) {
int spaceCount = 0, newLength, i = 0;
for (i = 0; i < length; i++)
{
if (str\[i\] == ‘ ‘)
{
spaceCount++;
}
}
newLength = length + spaceCount \* 2;
str\[newLength\] = ‘\\0’;
for (i = length - 1; i >= 0; i--)
{
if (str\[i\] == ‘ ‘)
{
str\[newLength - 1\] = ‘0’;
str\[newLength - 2\] = ‘2’;
str\[newLength - 3\] = ‘%’;
newLength = newLength - 3;
}
else
{
str\[newLength - 1\] = str\[i\];
newLength = newLength - 1;
}
}
}
Time Complexity: O(N), N is length of the string.
C code
Here is a c code doing the similar stuff, borrowed from here :
int main() {
char src\[\] = "helo b";
int len = 0, spaces = 0;
/\* Scan through src counting spaces and length at the same time \*/
while (src\[len\]) {
if (src\[len\] == ' ')
++spaces;
++len;
}
/\* Figure out how much space the new string needs (including 0-term) and allocate it \*/
int newLen = len + spaces\*2 + 1;
char \* dst = malloc(newLen);
/\* Scan through src and either copy chars or insert %20 in dst \*/
int srcIndex=0,dstIndex=0;
while (src\[srcIndex\]) {
if (src\[srcIndex\] == ' ') {
dst\[dstIndex++\]='%';
dst\[dstIndex++\]='2';
dst\[dstIndex++\]='0';
++srcIndex;
} else {
dst\[dstIndex++\] = src\[srcIndex++\];
}
}
dst\[dstIndex\] = '\\0';
/\* Print the result \*/
printf("New string: '%s'\\n", dst);
/\* And clean up \*/
free(dst);
return 0;
}
Point to note here is that when you are using malloc, set the last index to ‘\0’ as it is a c-style string OR you can use calloc.