Tuesday, October 16, 2012

String Replacement / String Removal !

Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

Variation:
Remove all occurrences of the given pattern/string from another string.
for example:

 char str[]="absbdababad";
  char pattern[]="ab";
then our function should return  "sbdad"


Strategy:

We should take advantage that the replacement is only one character in length. Assume that the pattern is at least one character in length, then the replacement’s length will never exceed the pattern’s length. This means that when we overwrite the existing string with replacement, we would never overwrite characters that would be read next.
Two pointers are also used for an efficient in-place replacement, which traverses the string once without any extra memory.

Code:

bool isMatch(char *str, const char* pattern) {
  while (*pattern)
    if (*str++ != *pattern++)
      return false;
  return true;
}

void replace(char str[], const char *pattern) {
  if (str == NULL || pattern == NULL) return;
  char *pSlow = str, *pFast = str;
  int pLen = strlen(pattern);
  while (*pFast != '\0') {
    bool matched = false;
    while (isMatch(pFast, pattern)) {
      matched = true;
      pFast += pLen;
    }
    if (matched)
      *pSlow++ = 'X';
    // tricky case to handle here:
    // pFast might be pointing to '\0',
    // and you don't want to increment past it
    if (*pFast != '\0')
      *pSlow++ = *pFast++;  // *p++ = (*p)++
  }
  // don't forget to add a null character at the end!
  *pSlow = '\0';
}

Test cases:

Format is string, pattern = answer)
-----------------------------------
a, a = X
aa, aa = X
aa, a = X
aa, aaa = aa
abc, abc = X
abcabc, abc = X
abcabcabc, abc = X
abcaabcaabc, abc = XaXaX
abcaaabcaaabca, abc = XaaXaaXa
abcabcabababcabc, abc = XababX
abcabcabababcabcab, abc = XababXab
aabbaabbaaabbbaabb, aabb = XaXbX
aabbaabbaaabbbaabb, aaabb = aabbaabbXbaabb
aabbaabbaaabbbaaabb, aaabb = aabbaabbXbX
aabbaabbaaabbbaaabc, aaabb = aabbaabbXbaaabc
abcdeffdfegabcabc, abc = XdeffdfegX
abcdeffdfegabcabc, ab = XcdeffdfegXcXc
abcdeffdfegabcabc, a = XbcdeffdfegXbcXbc
abcdeffdfegabcab, abc = XdeffdfegXab
abcdeffdfegabcabcab, abc = XdeffdfegXab
abcdeffdfegabcaabcab, abc = XdeffdfegXaXab
abcdeffdfegabcaaaabcab, abc = XdeffdfegXaaaXab
aaaaaa, a = X
aaaaaa, aa = X
aaaaaa, aaaaaa = X
aaaaaa, aaaaaaa = aaaaaa
aabaababaaab, a = XbXbXbXb
aabaababaaa, a = XbXbXbX
aaaab, a = Xb
baaa, a = bX
aabaaabaab, aaa = aabXbaab
aabaaabaab, aa = XbXabXb
aabaaabaa, aa = XbXabX

Variation:

In the above program we can keep the slow pointer at its place and continue the loop if matched is true

Code:

#include <iostream>
using namespace std;

bool isMatch(char *str, const char* pattern) {
  while (*pattern)
    if (*str++ != *pattern++)
      return false;
  return true;
}

void replace(char str[], const char *pattern) {
  if (str == NULL || pattern == NULL) return;
  char *pSlow = str, *pFast = str;
  int pLen = strlen(pattern);
  while (*pFast != '\0') {
    bool matched = false;
    while (isMatch(pFast, pattern)) {
      matched = true;
      pFast += pLen;
    }
    if (matched)
      continue;
     // *pSlow++ = 'X';
    // tricky case to handle here:
    // pFast might be pointing to '\0',
    // and you don't want to increment past it
    if (*pFast != '\0')
      *pSlow++ = *pFast++;  // *p++ = (*p)++
  }
  // don't forget to add a null character at the end!
  *pSlow = '\0';
}

int main()
{
  char str[]="absbdababad";
  char pattern[]="ab";
  replace(str, pattern);
  printf("\n%s",str);

  getchar();
  return 0;

}

No comments:

Post a Comment