This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/replace-all-spaces-in-c-style-string-with-20-/.
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.
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.
0 comments:
Post a Comment