fill in the comments for this peice of code c++ typedef struct LangData { string ch; // stores a single char int i; // index of char from the original string int start; // start index of substr int endInd; // end index of substr LangData(const string &ch, int i, int s, int e) : ch(ch), i(i), start(s), endInd(e) {} } LangData; // This function generates all strings of length at most k the language generated by the characters in the input string // Input: string in_str, int k // Output: list of all strings of length at most k, consisting of characters in input_str // List language(string input_str, int k) { List langList; langList.insert(""); for (int i = 1; i <= k; i++) { stack recurData; // Generate a blank strig of the required length string blankStr = ""; for (int j = 0; j < i; j++) blankStr += " "; // Push onto the stack recurData.push(LangData(blankStr, 0, 0, input_str.size() - 1)); while (recurData.size() > 0) { // Read top LangData top = recurData.top(); recurData.pop(); if (top.i == i) { // Add to list if the string is complete langList.insert(top.ch); } else { // Generate new entry for (int j = top.start; j <= top.endInd; j++) { // Copy the top LangData push = top; // Add new char from input push.ch[top.i] = input_str[j]; // Increment index push.i++; // Save to stack recurData.push(push); } } } } return langList; }
fill in the comments for this peice of code c++
typedef struct LangData {
string ch; // stores a single char
int i; // index of char from the original string
int start; // start index of substr
int endInd; // end index of substr
LangData(const string &ch, int i, int s, int e) : ch(ch), i(i), start(s), endInd(e) {}
} LangData;
// This function generates all strings of length at most k the language generated by the characters in the input string
// Input: string in_str, int k
// Output: list of all strings of length at most k, consisting of characters in input_str
//
List language(string input_str, int k) {
List langList;
langList.insert("");
for (int i = 1; i <= k; i++) {
stack<LangData> recurData;
// Generate a blank strig of the required length
string blankStr = "";
for (int j = 0; j < i; j++)
blankStr += " ";
// Push onto the stack
recurData.push(LangData(blankStr, 0, 0, input_str.size() - 1));
while (recurData.size() > 0) {
// Read top
LangData top = recurData.top();
recurData.pop();
if (top.i == i) {
// Add to list if the string is complete
langList.insert(top.ch);
} else {
// Generate new entry
for (int j = top.start; j <= top.endInd; j++) {
// Copy the top
LangData push = top;
// Add new char from input
push.ch[top.i] = input_str[j];
// Increment index
push.i++;
// Save to stack
recurData.push(push);
}
}
}
}
return langList;
}
Step by step
Solved in 2 steps with 2 images
