Все палиндромы строки

Классическая задачка, но не помню, есть ли она тут, добавим отдельной заметкой.

Дана строка s, требуется разделить её на части так, чтобы каждая отдельная строка была палиндромом (читалась одинаково слева направо и справа налево). Пробелы и другие разделители слов не игнорируются. Строка из одного символа также по определению считается палиндромом.

Нужно вернуть и/или напечатать все возможные палиндромные разбиения s.

Задача проверялась в консоли актуальной сборки Visual Studio 2019.

Решение без рекурсии, O(n²):

#include <iostream>
#include <string>
#include <vector>

bool check_palindrome(std::string s, int index, int i) {
 while (index <= i) {
  if (s[index++] != s[i--]) return 0;
 }
 return 1;
}

void the_helper(std::vector<std::vector<std::string> >& result,
 std::vector<std::string>& dump, std::string s, int n, int index) {
 //избегаем >=, потому что нам нужны только уникальные комбинации
 if (index == n) {
  result.push_back(dump);
  return;
 }
 for (int i = index; i < n; i++) {
  // если s.substr до индекса i является палиндромом
  if (check_palindrome(s, index, i)) {
   dump.push_back(s.substr(index, i - index + 1));
   the_helper(result, dump, s, n, i + 1);
   dump.pop_back(); //задний ход :)
  }
 }
}

int main() {
 std::string s = "amanaplanacanalpanama";
 int n = s.size();
 std::vector<std::vector<std::string>> result; //результаты
 std::vector<std::string> dump; //вектор-дамп, временный
 the_helper(result, dump, s, n, 0);
 int row_l = result.size();
 std::cout << "All Possible palindromic partitions of string" << std::endl;
 std::cout << "[";
 for (int i = 0; i < row_l; i++) {
  std::cout << "[" << (i + 1) << ": ";
  int m = result[i].size();
  for (int j = 0; j < m; j++) {
   if (j == m - 1) {
    std::cout << result[i][j];
    continue;
   }
   std::cout << result[i][j] << ",";
  }
  if (i == row_l - 1) {
   std::cout << "]";
   continue;
  }
  std::cout << "],";
 }
 std::cout << "]";
 return 0;
}

Решение с рекурсией.

#include <iostream>
#include <string>
#include <vector>

bool checkPalindrome(std::string str) { //палиндром или нет
 int len = str.length() - 1;
 for (int i = 0; i < len; i++) {
  if (str[i] != str[len]) return false;
  len--;
 }
 return true;
}

void printSolution(std::vector<std::vector<std::string>> partitions) {
 for (int i = 0; i < partitions.size(); ++i) {
  std::cout << (i+1) << ") ";
  for (int j = 0; j < partitions[i].size(); ++j)
   std::cout << partitions[i][j] << " ";
  std::cout << std::endl;
 }
 return;
}

//Проходим по всем индексам и рекурсивно добавляем оставшиеся
//части, если текущая std::string является палиндромом.
void addStrings(std::vector<std::vector<std::string> >& v, std::string& s,
 std::vector<std::string>& temp, int index) {
 int len = s.length();
 std::string str;
 std::vector<std::string> current = temp;
 if (index == 0) temp.clear();
 for (int i = index; i < len; ++i) {
  str = str + s[i];
  if (checkPalindrome(str)) {
   temp.push_back(str);
   if (i + 1 < len) addStrings(v, s, temp, i + 1);
   else v.push_back(temp);
   temp = current;
  }
 }
 return;
}

void partition(std::string s, std::vector<std::vector<std::string>> &v) {
 //Генерирует все палиндромы из s и сохраняет результат в v
 std::vector<std::string> temp;
 addStrings(v, s, temp, 0);
 return;
}

int main() {
 std::string s = "amanaplanacanalpanama";
 std::vector<std::vector<std::string> > partitions;
 partition (s, partitions);
 printSolution (partitions);
 return 0;
}

В обоих случаях получилось по 92 разбиения. И помните - итерация и рекурсия взаимозаменяемы всегда.

04.02.2023, 14:43 [306 просмотров]