# Sword finger Offer learning summary - string arrangement

This series is the learning summary of sword finger Offer, mainly the analysis and implementation of code cases:

Book links: http://product.dangdang.com/24242724.html

Original author's blog: http://zhedahht.blog.163.com/blog/static/254111742011101624433132/

The original author blog link has a complete project code download.

## Arrangement of strings

### subject

Title: enter a string and print out all the permutations of characters in the string. For example, the input string a b c will print out all the strings abc, a c b, bac, b c A, cab and cba that can be arranged by the characters a, b and c.

### Conventional solution:

From our simplest thinking, if we follow the normal mathematical method, we should first consider the first, then look at the second, then look at the next and so on.

In fact, we should be sensitive to these things when we make a long run. First of all, then, these remind us to divide and rule.

This is not easy to do in code in a mathematical way. Below is the C code of the full permutation problem of LeetCode.

Leetcode 46. There are no duplicate characters.

```
public class Solution
{
public IList<IList<int>> Permute(int[] nums)
{
IList<IList<int>> result = new List<IList<int>>();
IList<int> list = new List<int>();
helper(result, list, nums);
return result;
}
private void helper(IList<IList<int>> result, IList<int> list, int[] nums)
{
if (list.Count == nums.Length)
{
if (!result.Contains(list))
{
result.Add(new List<int>(list));
return;
}
}
for (int i = 0; i < nums.Length; i++)//Fix the first to the n th array first
{
if (list.Contains(nums[i]))
{
continue;
}
if(!list.Contains(nums[i]))
list.Add(nums[i]);
helper(result, list, nums);
list.RemoveAt(list.Count - 1);//Remove the difference according to the index
//list.Remove(list.Count - 1); / / remove the range starting from
}
}
}
```

### Solution of exchange:

We can think of a string as consisting of two parts: the first part is its first character, and the second part is all the following characters. In the figure below, we distinguish two parts of the string with two different background colors.

Finding the arrangement of the whole string can be seen as two steps

Step 1. First, find all possible characters in the first position, that is, exchange the first character with all subsequent characters

Step 2. Then repeat this step by dividing the following characters into two parts.

```
void Permutation(char* pStr)
{
if(pStr == NULL)
return;
Permutation(pStr, pStr);
}
void Permutation(char* pStr, char* pBegin)
{
if (*pBegin == '\0')
{
printf("%s\n", pStr);
}
else
{
//Fixed first character
for (char* pCh = pBegin; *pCh != '\0'; ++pCh)
{
//Exchange the first character with the next character
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
//After that, exchange the first character and the following character back
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
```