剑指Offer面试题:26.字符串的排列

一、题目:字符串的排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

二、解题思路

2.1 核心步骤

  我们可以把一个字符串看成由两部分组成:第一部分为它的第一个字符,第二部分是后面的所有字符。在下图中,我们用两种不同的背景颜色区分字符串的两部分。

Step1.把字符串分为两部分,一部分是字符串的第一个字符,另一部分是第一个字符以后的所有字符(有阴影背景的区域)。

Step2.接下来我们求阴影部分的字符串的排列,拿第一个字符和它后面的字符逐个交换。

2.2 代码实现

    public static void Permutation(char[] str)
    {
        if (str == null)
        {
            return;
        }

        Permutation(str, str, 0);
    }

    public static void Permutation(char[] str, char[] begin, int startIndex)
    {
        if (startIndex == str.Length)
        {
            Console.WriteLine(str);
        }
        else
        {
            for (int i = startIndex; i < str.Length; i++)
            {
                char temp = begin[i];
                begin[i] = begin[startIndex];
                begin[startIndex] = temp;

                Permutation(str, begin, startIndex + 1);

                temp = begin[i];
                begin[i] = begin[startIndex];
                begin[startIndex] = temp;
            }
        }
    }

三、单元测试

3.1 测试用例

  (1)封装测试辅助方法

    public static void TestPortal(string str)
    {
        if (string.IsNullOrEmpty(str))
        {
            Console.WriteLine("Test for NULL begins:");
            Permutation(null);
        }
        else
        {
            Console.WriteLine("Test for {0} begins:", str);
            Permutation(str.ToCharArray());
        }

        Console.WriteLine();
    }

  (2)功能测试、特殊输入测试

    public static void Test1()
    {
        TestPortal(null);
    }

    public static void Test2()
    {
        string str = "";
        TestPortal(str);
    }

    public static void Test3()
    {
        string str = "a";
        TestPortal(str);
    }

    public static void Test4()
    {
        string str = "ab";
        TestPortal(str);
    }

    public static void Test5()
    {
        string str = "abc";
        TestPortal(str);
    }

3.2 测试结果

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏racaljk

Julia体验 语言基础

以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

23320
来自专栏Golang语言社区

【Go 语言社区】解析Go语言编程中的struct结构

struct和C语言的很相似,模拟出class的功能,但是不完全的!没有构造函数等! struct的申明 package main import "fmt" t...

35260
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

34880
来自专栏Golang语言社区

实效go编程--2

Go函数的返回值或结果“形参”可被命名,并作为常规变量使用,就像传入的形参一样。 命名后,一旦该函数开始执行,它们就会被初始化为与其类型相应的零值; 若该函数执...

35470
来自专栏小灰灰

# Java 一步一步实现高逼格的字符串替换工具(二)

Java 一步一步实现高逼格的字符串替换工具(二) 上一篇实现了一个用于字符串替换的方法,主要是利用 正则 + jdk的字符串替换,本篇则会再之前的基础上...

25960
来自专栏菩提树下的杨过

XmlWriter/XmlReader示例代码

在Silverlight项目中,如果您想最大程度的减少xap包的大小,仅使用默认System.Xml命名空间下提供的功能来实现“XML序列化/反序列化”,恐怕X...

24570
来自专栏小樱的经验随笔

洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数...

32850
来自专栏chenssy

【死磕 Spring】—– IOC 之构造函数实例化 bean

createBeanInstance() 用于实例化 bean,它会根据不同情况选择不同的实例化策略来完成 bean 的初始化,主要包括:

16340
来自专栏技术之路

精典算法之二分查找法

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列...

22470
来自专栏跟着阿笨一起玩NET

VB.NET语法小结

28420

扫码关注云+社区

领取腾讯云代金券