博客

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出

来的所有字符串 abc,acb,bac,bca,cab 和 cba

观察字符串

abc acb bac cab cba

可以发现是

有3个字母，分别以每一个字母做为第一个，然后再以不是这个字母的剩下两个字母作为子问题的第一个得到的解。

也就是说，我们把这个问题转换成选一个没有重复的字母做为第一个，然后缩小区间，把剩下两个字母当作是一个全新的问题，不断循环直到问题解决

那么我们要解决的问题就是：选择一个字母放到第一个的位置。子问题是再选择一个不重复的字母放到子问题的第一个位置。以此类推。

这里实际上体现了一个思想：就是我们把字符串的问题转换成了用一颗多叉树解决的问题

先看一下代码吧

class Solution{
public:
     void Swap(string&str, int i, int j)
     {
         char temp = str[i];
         str[i] = str[j];
         str[j] = temp;
     }
     
     bool isEx(string&str, vector<string>&result)
     {
         for(auto it = result.begin(); it != result.end(); it++)
         {
             if(str == *it)
             {
                 return true;
             }
         }
         return false;
     }
     void PermutationHelper(string&str, vector<string>&result, int start)
     {
         if(start == str.size())
         {
             if(!isEx(str,result)
             {
                 result.push_back(str);
             }
         }
         for(int i = start; i < str.size(); ++i)//这里的i是为了让问题的其实进行不断的变化
         {
             swap(str, start, i)
             PermutationHelper(str, result, start + 1);//这里是为了把问题不断拆分成子问题
             swap(str, start, i)
         }
     }
     vector<string> Permutation(string&str)
     {
         vector<string> result;
         if(str.size() > 0)
         {
             PermutationHelper(str, result, 0);
         }
         return result;
     } 

先了解哪里用了回溯算法了？

答案是递归过后的swap这里是一个回溯的过程，我们可以想象一下，我们为什么要使用这个for循环，for循环是为了宽度，递归是深度遍历，是为了深度。我们如果把这个字符串当作成为一棵多叉树的话，那么这个递归就是DFS深度优先遍历。如果这棵树是二叉树的话，那么递归方式就是root->left和root->right递归就可以了。但是正因为这是一颗多叉树，所以我们不可以这样遍历，多叉树的遍历方式应该是通过某种媒介让一枝变成多枝。没有循环就是一枝不断深入，循环可以让其变成多枝。

没有循环的话那么从头到尾都将是一枝。 所以循环的作用是让子问题分叉。

循环让树变宽，递归让其变深。