Java递归实现字符串的排列和组合

我们在笔试中经常会遇到需要对字符串进行排列或者组合的题目。本篇文章对字符串的排列和组合进行递归版本的实现。

1. 字符串的组合

题目:输入一个字符串,输出该字符串中字符的所有组合。

例子:输入:abc,它的组合有:a、b、c、ab、ac、bc、abc

分析:我们可以将字符串中的每个字符看成二叉树的一个节点,根节点为空,每个节点都会有两种选择:要 和 不要 两种选择 。那么我们就可以利用递归实现。

  • 代码实现:
package com.offer.manongqiuzhi.String;
/** * @author pcwl * @description:递归实现字符串的组合 */public class CombinationString {
    public static void printAllSubString(String str){        if(str == null){            return;        }
        char[] chars = str.toCharArray();        if(chars.length > 0){            String pre = new String("");   // pre:用于表示从0到i-1位置上形成的结果            printAllSubString(0, pre, chars);        }else{            System.out.println("");     // 输入空字符串也会打印空        }    }
    public static void printAllSubString(int i, String pre, char[] chars){        // 迭代终止条件        if(i == chars.length){            // 说明已经到最后一个字符了,所有的选择都已经做完了,应该返回了            System.out.println(pre);            return;        }
        // 如果没有到最后一个字符,那么当前字符有两种选择:选择要 和 选择不要        printAllSubString(i + 1, pre, chars);  // 不要当前字符        printAllSubString(i + 1, pre + String.valueOf(chars[i]), chars);   // 要当前字符    }
    // 测试    public static void main(String[] args) {        printAllSubString("abc");    }}

运行结果:

2. 字符串的排列

01

全排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。

举例:输入字符串 abc,则输出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

分析:排列和上面的组合问题思想是一样的:上面的组合问题,每个节点只有 “要” 和 “不要” 两种选择,而排列这里每个节点 i 有 n - i 种选择。

排列问题:所有的排列都是包含该字符串中所有的字符,所以不需要像组合那样利用额外的空间 pre 记录选择的过程。

需要注意的是:i 位置在进行选择的时候,会先和 i + 1 位置交换位置,搞定 i + 1 后面的排列后,会再和 i + 2 ~ n - 1 位置上的每个元素交换一次,所以为了保证都是和 i 位置上的元素进行交换,每次递归一次后,必须要将 i 位置元素再换回原来的位置。

可以直观的理解下:加入现在搞定 i 位置上元素,i 一共有 n - i 种选择,每次 i 位置固定后,i + 1 ~ n - 1 位置上的元素都是同样递归实现。

  • 代码实现:
package com.offer.manongqiuzhi.String;
/** * @author pcwl * @description:递归实现全排列 */public class PermutationString {    public static void printAllSort(String string){        if(string == null){            return;        }
        char[] chars = string.toCharArray();        if(chars.length > 0){            printAllSort(0, chars);        }    }
    // 对i及i以后的字符进行全排列    public static void printAllSort(int i, char[] chars){        // 递归终止条件        if(i == chars.length){            System.out.println(String.valueOf(chars));        }
        for(int j = i; j < chars.length; j++){            swap(i, j, chars);   // 第 i 个位置有 i ~ (n - 1) 种选择。n 为字符串的长度            printAllSort(i + 1, chars);            swap(i, j, chars);   // 保证 i 后面的字符每次都是和 i 位置上的元素进行的交换,还需要将 i 和 j 交换回来        }    }
    public static void swap(int i, int j, char[] chars){        int temp = chars[i];        chars[i] = chars[j];        chars[j] = chars[i];    }
    public static void main(String[] args) {        printAllSort("abcc");    }}

运行结果:

02

去重全排列

只需要增加一个 hashset,用于保证重复字符不会被再次交换。

package com.offer.manongqiuzhi.String;
import java.util.HashSet;
/** * @author pcwl * @description:递归实现全排列(去重) */public class StringByRemoveDuplicate {    public static void printAllSort(String string){        if(string == null){            return;        }
        char[] chars = string.toCharArray();        if(chars.length > 0){            printAllSort(0, chars);        }    }
    // 对i及i以后的字符进行全排列    public static void printAllSort(int i, char[] chars){        // 递归终止条件        if(i == chars.length){            System.out.println(String.valueOf(chars));        }
        // 用于保证每次交换的字符不存在重复的字符        HashSet<Character> set = new HashSet<>();        for(int j = i; j < chars.length; j++){            if(!set.contains(chars[j])){                set.add(chars[j]);                // 第 i 个位置有 i ~ (n - 1) 种选择。n 为字符串的长度                swap(i, j, chars);                printAllSort(i + 1, chars);                // 保证 i 后面的字符每次都是和 i 位置上的元素进行的交换,还需要将 i 和 j 交换回来                swap(i, j, chars);            }        }    }
    public static void swap(int i, int j, char[] chars){        int temp = chars[i];        chars[i] = chars[j];        chars[j] = chars[i];    }
    public static void main(String[] args) {        printAllSort("abcc");    }}

运行结果:

-------- END ---------

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-22

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏全栈修仙之路

深入学习 Node.js Net

网络上的两个程序通过一个双向的通信连接实现数据的交换,这个连接的一端称为一个 socket(套接字),因此建立网络通信连接至少要一对端口号。socket 本质是...

6520
来自专栏Java技术栈

20 亿的 URL 集合,如何快速判断其中一个?

假设遇到这样一个问题:一个网站有 20 亿 url 存在一个黑名单中,这个黑名单要怎么存?若此时随便输入一个 url,你如何快速判断该 url 是否在这个黑名单...

6920
来自专栏Jerry的SAP技术分享

一段让人瑟瑟发抖的ABAP代码

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

6830
来自专栏全栈修仙之路

RxJS Observable

这两个模式是 Observable 的基础,下面我们先来介绍一下 Observer Pattern。

8920
来自专栏小皮咖

浏览器 Event Loop 机制

event loop是一个执行模型,在不同的地方有不同的实现。浏览器和NodeJS基于不同的技术实现了各自的Event Loop。

9920
来自专栏小皮咖

daily-question-02(前端每日一题02)

在这里记录着每天自己遇到的一道印象深刻的前端问题,以及一道生活中随处可见的小问题。

7630
来自专栏全栈修仙之路

RxJS 函数式与响应式编程

简单说,”函数式编程”是一种 “编程范式”(programming paradigm),也就是如何编写程序的方法论。

9620
来自专栏磐创AI技术团队的专栏

ICCV 2019 | 用于提高车牌识别的单幅噪声图像去噪和校正

下面要介绍的论文始发于ICCV2019,题为「SNIDER: Single Noisy Image Denoising and Rectification fo...

14210
来自专栏磐创AI技术团队的专栏

理解BERT:一个突破性NLP框架的综合指南

想象一下——你正在从事一个非常酷的数据科学项目,并且应用了最新的最先进的库来获得一个好的结果!几天后,一个新的最先进的框架出现了,它有可能进一步改进你的模型。

11130
来自专栏全栈修仙之路

TypeScript 简介及编码规范

TypeScript 是一种由微软开发的自由和开源的编程语言。它是 JavaScript 的一个超集,而且本质上向这个语言添加了可选的静态类型和基于类的面向对象...

16440

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励