c++ - 返回字符串的所有子字符串的递归函数

Question

我需要用C++实现一个函数，

vector<string> generateSubstrings(string s),

返回一个字符串的所有子字符串的 vector 。比如字符串“rum”的子串就是七个字符串

“r”、“ru”、“rum”、“u”、“um”、“m”、“”。

该函数必须是递归的，并且必须以 vector 形式返回结果。

到目前为止，这是我的代码。它只打印“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";
}

Answer 1

在你的作业中写着递归函数必须像这样声明

vector<string> generateSubstrings(string s),

但是你正试图使另一个函数递归声明为 like

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 );

您还可以用插入方法替换所示函数中的循环。例如

#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;
}

程序输出将与上图相同。

这是一个程序修改，在 vector 中包含一个空字符串。

#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;
}