In một chuỗi gần nhất không chứa các bản sao liền kề trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi. Nhiệm vụ của chúng ta là in một chuỗi gần nhất với chuỗi hiện tại và không chứa bất kỳ ký tự trùng lặp nào liền kề.

Hãy lấy một ví dụ để hiểu vấn đề

Input: string = “good”
Output: goad

Trong ví dụ này, chúng tôi thấy rằng các phần tử ở chỉ mục 1 và 2 là giống nhau, vì vậy chúng tôi thay đổi các phần tử ở chỉ mục 2.

Để giải quyết vấn đề này, chúng ta sẽ duyệt qua chuỗi và kiểm tra xem có hai phần tử liền kề nào giống nhau không. Nếu có thì đổi phần tử thứ 2 (nếu i và i + 1 phần tử giống nhau thì đổi i + 1 phần tử). Việc giải quyết điều này sẽ sử dụng thuật toán tham lam và đối với mỗi cặp phần tử tương tự liền kề, chúng ta sẽ thực hiện một thay đổi. Một điều chúng ta phải ghi nhớ là kiểm tra tất cả các phần tử lân cận trong khi thay đổi, tức là nếu chúng ta đang thay đổi phần tử thứ i hơn là sau khi thay đổi i + 1 và phần tử chỉ mục của tôi phải khác.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include <iostream>
#include <string.h>
using namespace std;
void printStringWithNoDuplicates(string str){
   int len = str.length();
   for (int i = 1; i < len; i++){
      if (str[i] == str[i - 1]){
         str[i] = 'a';
         while (str[i] == str[i - 1] || (i + 1 < len && str[i] == str[i + 1])) str[i]++;
         i++;
      }
   }
   cout<<str;
}
int main(){
   string str = "good";
   cout<<"The orignal string is : "<<str<<endl;
   cout<<"String without adjecent duplicate characters is : ";
   printStringWithNoDuplicates(str);
   return 0;
}

Đầu ra

The orignal string is : good
String without adjecent duplicate characters is : goad