Question

C++ (using recursion or stacks)

• List stretch (string input, int k). A stretch of the input string is generated by repeating each character in order up to k times (and at least once). For input string "abc" and k = 2, the output list should have: abc, aabc, abbc, abcc, aabbc, aabcc, abbcc, aabbcc. (Again, the order does not matter.)

Answer 1

Screenshot of the code:

//Include the header files. #include <list> #include <vector> #include <algorithm> #include <iterator> #include <iostream> using namespace std; //Make the typing easier. using ULL = unsigned long long; //Define the function to stretch the string by k. list<string> stretch (string input, size tk) //Declare the variable to store the result. list<string> result{ input }; //Traverse the string. for (size t depth = OU; depth < k-1; ++depth) { for (ULL subSetID = BULL ; subSetID < (IULL << static cast<ULL>(input.size())); ++subSetID) { ULL bitMask{ IULL }; string temp{ }; ////Traverse the string. for (const char letter : input) { temp += std::string(1, letter) + (((subsetID & bitMask) == bitMask) ? std::string (depth +. 1, letter) : ""); //Check the next bit. bitMask «<= 1; result.push back (temp); //Return the result. return result;

//Define the main function. int main() { //Test the string as per the given example. list<string> l{ stretch ("abc",2) }; //Display the result. copy (1.begin(), l.end(), ostream iterator<std::string>(cout, "\n")); //Return the value for the main function. return 0;

Sample Output:

abc aabc abbc aabbc abcc aabcc abbcc aabbcc

Code To Copy:

//Include the header files.

#include <list>

#include <vector>

#include <algorithm>

#include <iterator>

#include <iostream>

using namespace std;

//Make the typing easier.

using ULL = unsigned long long;

//Define the function to stretch the string by k.

list<string> stretch(string input, size_t k)

{

    //Declare the variable to store the result.

    list<string> result{ input };

    //Traverse the string.

    for (size_t depth = 0U; depth < k-1; ++depth) {

    

        for (ULL subSetID = 1ULL ; subSetID < (1ULL <<

static_cast<ULL>(input.size())); ++subSetID) {

            ULL bitMask{ 1ULL };

       

            string temp{};

            ////Traverse the string.

            for (const char letter : input) {

                temp += std::string(1, letter) + (((subSetID &

bitMask) == bitMask) ? std::string(depth +

1, letter) : "");

                //Check the next bit.

                bitMask <<= 1;

            }

          

            result.push_back(temp);    

        }

    }

    //Return the result.

    return result;

}

//Define the main function.

int main() {

    //Test the string as per the given example.

    list<string> l{ stretch("abc",2) };

    //Display the result.

    copy(l.begin(), l.end(),

ostream_iterator<std::string>(cout, "\n"));

    //Return the value for the main function.

    return 0;

   

}

//To test any string, put it in the main function along with the value of k.