C++实现分割回文串 |21xrx.com

C++实现分割回文串

2023-06-29 03:50:58 深夜i 9 0

C++ 分割回文串

回文串是指正序和倒序都一样的字符串，例如“level”、“madam”和“racecar”等。分割回文串是指将一个字符串分割成若干个回文串，使得每个回文串的长度都大于0。本文介绍如何使用C++实现分割回文串。

实现思路：

1. 定义一个函数isPalindrome，用于判断一个字符串是否为回文串。

2. 定义一个递归函数partition，分别枚举当前位置和分割点，若当前子串为回文串，将其作为下一个递归调用的参数，直到分割到字符串末尾为止。

代码实现：

c++
#include <iostream>
#include <vector>
using namespace std;
bool isPalindrome(const string& s, int start, int end)
{
  while(start < end)
  {
    if(s[start] != s[end])
      return false;
    start++;
    end--;
  }
  return true;
}
void partition(string& s, int start, vector<string>& path, vector<vector<string>>& result)
{
  // 如果start等于字符串的长度，说明已经分割完了整个字符串，将当前结果加入到结果集中
  if(start == s.length())
  {
    result.push_back(path);
    return;
  }
  // 从start位置开始，分别枚举分割点
  for(int i = start; i < s.length(); i++)
  {
    // 如果当前子串是回文串
    if(isPalindrome(s, start, i))
    {
      // 将当前子串加入到路径中
      path.push_back(s.substr(start, i - start + 1));
      // 递归处理下一个子串
      partition(s, i + 1, path, result);
      // 回溯，将当前子串从路径中移除
      path.pop_back();
    }
  }
}
vector<vector<string>> partition(string s)
{
  vector<vector<string>> result;
  vector<string> path;
  partition(s, 0, path, result);
  return result;
}
int main()
{
  string s = "aab";
  vector<vector<string>> result = partition(s);
  for(auto v : result)
  {
    for(auto s : v)
      cout<<s<<" ";
    cout<<endl;
  }
  return 0;
}

样例输出：

c++ a a b aa b

总结：

本文介绍了如何使用C++实现分割回文串的算法。关键在于判断一个子串是否为回文串和在枚举分割点的过程中递归处理下一个子串，回溯时将当前子串从路径中移除。

上一篇: idea打包java可执行jar包

下一篇: C++三大特点解析

评论区

相似文章