« Pair star

Problem

Given a string S, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*".

Input format :

String S

Output format :

Modified string

Constraints :

0 <= |S| <= 1000

where |S| represents length of string S.

Sample Input 1 :

hello

Sample Output 1:

hel*lo

Sample Input 2 :

aaaa

Sample Output 2 :

a*a*a*a

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int length(char input[])
15{
16    int len = 0;
17    for (int i = 0; input[i] != '\0'; i++)
18    {
19        len++;
20    }
21    return len;
22}
23
24void pairStar(char input[], int start)
25{
26    if (input[start] == '\0' || input[start + 1] == '\0')
27    {
28        return;
29    }
30    pairStar(input, start + 1);
31    if (input[start] == input[start + 1])
32    {
33        int len = length(input);
34        for (int i = len - 1; i >= start + 1; i--)
35        {
36            input[i + 1] = input[i];
37        }
38        input[len + 1] = '\0';
39        input[start + 1] = '*';
40    }
41}
42
43void pairStar(char input[])
44{
45    pairStar(input, 0);
46}
47
48int main()
49{
50    char input[100];
51    cin.getline(input, 100);
52    pairStar(input);
53    cout << input << endl;
54    return 0;
55}