数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究打印给定字符串的所有排列
打印给定字符串的所有排列是回溯问题的示例。我们将减小子字符串的大小以解决子问题，然后再回溯以从该部分中获得另一个排列。
例如，如果字符串为 ABC，则所有排列将为 ABC、ACB、BAC、BCA、CAB、CBA。
此算法的复杂性为 O(n!)。这是一个非常高的复杂性。当字符串大小增加时，完成任务所需的时间就更长。
输入和输出
Input: A string “ABC” Output: All permutations of ABC is: ABC ACB BAC BCA CBA CAB
算法
stringPermutation(str, left, right)
输入：字符的字符串和左右索引。
输出：打印字符串的所有排列。
Begin if left = right, then display str else for i := left to right, do swap str[left] and str[i] stringPermutation(str, left+1, right) swap str[left] and str[i] //for backtrack done End
示例
#include<iostream>
using namespace std;
void stringPermutation(string str, int left, int right) {
if(left == right)
cout << str << endl;
else {
for(int i = left; i<= right; i++) {
swap(str[left], str[i]);
stringPermutation(str, left + 1, right);
swap(str[left], str[i]); //swap back for backtracking
}
}
}
int main() {
string str = "ABC";
cout << "All permutations of " << str << " is: " <<endl<<endl;
stringPermutation(str, 0, str.size()-1);
}
输出
All permutations of ABC is: ABC ACB BAC BCA CBA CAB
更新于： 2020 年 6 月 17 日
2K+ 浏览量
广告