C++ implements the method of replacing a character in one string with another

  • 2020-04-02 02:47:24
  • OfStack

This article illustrates a C++ method to replace one character in a string with another. Specific methods are as follows:

Title requirements:

Replace each space in the in-place implementation string with "%20", for example, input "We are happy", output "We%20are%20happy"
The replaced string is of course not just a space, but an example
This is a very good topic, is also a question in the baidu interview, the topic is not difficult, but the question must be considered comprehensively. Here is the following implementation code:


#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int findNumberFirst(const char *str, const char *dest, vector<int>& pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int pos = 0;
 int lenStr = strlen(str);
 int lenDest = strlen(dest);

 if (lenStr < lenDest)
 return 0;

 int count = 0;
 while (pos <= lenStr - lenDest)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pvec.push_back(pos);
  pos += lenDest;
  count++;
 }
 else
 {
  pos++;
 }
 }

 return count;
}

int findNumberLast(const char *str, const char *dest, vector<int> &pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int strLen = strlen(str);
 int destLen = strlen(dest);

 if (strLen < destLen)
 return 0;

 int pos = 0;
 while (pos <= strLen - destLen)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pos += destLen;
  pvec.push_back(pos - 1);
 }
 else
 {
  pos++;
 }
 
 }

 return pvec.size();
}

void replaceArray(char *str, const char *src, const char *dest)
{
 if (str == NULL || src == NULL || dest == NULL)
 return;

 vector<int> pvec;
 int strLen = strlen(str);
 int srcLen = strlen(src);
 int destLen = strlen(dest);

 if (strLen < srcLen)
 return;

 int posBefore = 0;
 int posAfter = 0;

 if (srcLen < destLen)
 {
 int count = findNumberLast(str, src, pvec);
 if (count <= 0)
  return;
 
 posAfter = strLen + count * (destLen - srcLen) - 1;
 posBefore = strLen - 1;

 while (count > 0 && posBefore >= 0)
 {
  if (pvec[count - 1] == posBefore)
  {
  posAfter -= destLen;
  strncpy(str + posAfter + 1, dest, strlen(dest));
  count--;
  posBefore--;
  }
  else
  {
  str[posAfter--] = str[posBefore--];
  }
 }
 }
 else if (strLen > destLen)
 {
 int count = findNumberFirst(str, src, pvec);
 if (count <= 0)
  return;

 posAfter = 0;
 posBefore = 0;

 int i = 0;
 while (count >= 0 && posBefore < strLen)
 {
  if (count > 0 && pvec[i] == posBefore)
  {
  strncpy(str + posAfter, dest, strlen(dest));
  posAfter += destLen;
  count--;
  posBefore += srcLen;
  i++;
  }
  else
  {
  str[posAfter++] = str[posBefore++];
  }
 }
 str[posAfter] = '0';
 }
}

void main()
{ 
 char *str = new char[100];
 if (str == NULL)
 return;
 memset(str, '0', 100);

 const char *src = " ";
 const char *dest = "%20";
//Case1: only one space
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case2: two Spaces
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case3: normal
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case3: space first
 strcpy(str, " we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case4: after the space
 strcpy(str, "we are happy ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case4: no Spaces
 strcpy(str, "wearehappy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//Case5: same on both sides
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 src = "%20";
 assert(dest == "%20");
 replaceArray(str, dest, src);
 cout << "str: " << str << endl;
}

One of the interesting things about analyzing the above code is that srcLen and destLen are either large or small, and their boundary conditions are determined differently. For example, if we are happy, if we copy back, count=2.

At count=0, the preceding space is exactly replaced, and we do not have to repeat the copy. But for copy from front to back, when count=0, the happy on the back side will not be copied.

I hope the examples described in this paper are helpful to the learning of C++ programming algorithm design.


Related articles: