C++에서 주어진 하위 문자열을 재귀적으로 삭제하여 문자열이 비게 될 수 있는지 확인

<시간/>

str1과 str2라는 두 개의 문자열이 주어졌다고 가정합니다. str2는 str1의 부분 문자열이고 str1에서 str2를 삭제할 수 있습니다. str2 문자열이 str1에 여러 번 나타날 수 있습니다. 여기서 우리의 목표는 str1에서 str2를 여러 번 제거하면 str1이 null 문자열이 되는지 알아내는 것입니다. 가능하면 1을 반환하고 그렇지 않으면 0을 반환합니다.

따라서 입력이 str1 ="CCCPPPPPP"와 같으면 str2 ="CPP"; 그러면 출력이 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

str1의 크기가 0인 동안 −
- index :=str1에서 str2의 문자열 시작 위치를 반환
- 인덱스가 -1과 같으면 -
  - 루프에서 빠져나오기
- str1에서 str2 삭제
str1의 크기가 0과 비슷하면 1을 반환하고 그렇지 않으면 0을 반환합니다.

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include<bits/stdc++.h>
using namespace std;
bool solve(string str1, string str2) {
   while (str1.size() > 0) {
      int index = str1.find(str2);
      if (index == -1)
      break;
      str1.erase(index, str2.size());
   }
   return (str1.size() == 0);
}
int main() {
   string str1 = "CCCPPPPPP", str2 = "CPP";
   cout<<solve(str1, str2)<<endl;
   return 0;
}

입력

"CCCPPPPPP", "CPP"