返回字符串的所有子字符串的递归函数
我需要在C++中实现一个函数，
vector<string> generateSubstrings(string s),它返回一个字符串的所有子字符串的向量。例如，字符串“rum”的子字符串是七个字符串
“r”“ru”“rum”“u”“um”“m”“。
函数必须是递归的，并且必须以向量的形式返回结果。
到目前为止，这是我的代码。它只打印"r“、"ru”和"rm“。我在实现这个函数时遇到了很多问题。我在过去的几个小时里一直在做这件事，但我就是想不出如何让它像所说的那样工作，所以任何帮助都将不胜感激。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> generateSubstrings(string s, int num){
int index = num;
int SIZE = s.size();
vector<string> substrings;
if(index == s.size()){//BASE CASE
string temp = s.substr(index,1);
substrings.push_back(temp);
}
else{
for(int i = 0; i < SIZE; ++i){
string temp = s.at(index) + s.substr(i,i);
substrings.push_back(temp);
}
generateSubstrings(s, num + 1);
}
return substrings;
}
int main() {
vector<string> vec(20);
vec = generateSubstrings("rum", 0);
cout << endl << endl;cout << "PRINTING VECTOR" << endl;
for ( int i = 0; i<vec.size();++i){
cout << vec.at(i);
cout << endl;
}
cout << "DONE";
}回答 3
Stack Overflow用户
发布于 2015-03-24 17:12:15
在你的赋值中，写着递归函数必须声明如下
vector<string> generateSubstrings(string s),但是您正在尝试使另一个函数递归，该函数声明如下
vector<string> generateSubstrings(string s, int num);因此，在任何情况下，您的解决方案都不能满足分配的要求。
该函数可能如下所示
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return {};
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
for ( const std::string &t : generateSubstrings( s.substr( 1 ) ) )
{
v.push_back( t );
}
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}它的输出是
r
ru
rum
u
um
m如果您还需要包含一个空字符串，则应该更改条件
if ( s.empty() ) return {};以适当的方式。例如
if ( s.empty() ) return { "" };同样，在这种情况下，您应该编写
v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );您还可以将所示函数中的循环替换为方法insert。例如
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return {};
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );
v.insert( v.end(), v2.begin(), v2.end() );
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}程序输出将与上面显示的相同。
下面是在向量中包含一个空字符串的程序修改。
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return { "" };
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );
v.insert( v.end(), v2.begin(), v2.end() );
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}Stack Overflow用户
发布于 2015-03-24 17:01:54
以下是使用Python的答案。它会打印"rum“的正确结果，但对于"rumm”，它会打印两个"m“子字符串，原因很明显：
def substrings(s):
result = []
if len(s) == 0:
result.append("")
if len(s) > 0:
result += substrings(s[1:])
for n in range(1,len(s)+1):
result.append(s[0:n])
return result
print substrings("rum")
print substrings("rumm")该算法的思想如下:对于"rum"，子串是"um“的子串，后跟"r”、"ru“和"rum”。对于"um"，子字符串是"m“后跟"u”和"um“的子串。对于"m"，子字符串是"“后跟"m”的子字符串。对于""，子字符串就是"“。所以，最后的列表是""，"m"，"u"，"um"，"r"，"ru"，"rum“。
尽管这不是C++，但您应该能够将代码转换为C++。但这可能不是您想要的，因为"rumm“有两个"m”子串。如果你认为"rumm“应该只有一个"m”子串，请留下评论，我会发布另一个答案。
Stack Overflow用户
发布于 2015-03-24 17:54:48
首先，你应该注意代码缩进。然后，我不看你的代码，我写了一些代码来实现你的目标，如下所示：
void generateSubstrings(string s, int num, vector<string> &sta)
{
if (num == s.size())
return;
auto b = begin(s) + num;
string temp = "";
temp += *b;
sta.push_back(temp);
b++;
while (b != end(s))
{
temp += *b;
sta.push_back(temp);
b++;
}
generateSubstrings(s, num + 1, sta);
}https://stackoverflow.com/questions/29228192
复制相似问题