全排列问题

野生程序员 Life is fucking movie ,we all performer !We all no more younger! 本文由博客端 http://localhost 主动推送

在各种算法竞赛,或者是笔试面试的过程中,全排列问题非常常见,列举一下一个经典的全排列问题,以遍后期巩固
剑指 Offer 38. 字符串的排列:

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


示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]
这是一个典型的全排列问题,那么遇到全排列问题我们到底该如何处理呢?
  1. 首先我们就想到了递归
  2. 然后我们需要一个辅助数组
  3. 然后我们还用到了回溯算法

我们可以用一个数组 boolean used [ ] 来表示当前位置的字符是否使用过,如果使用过的话那么我们进行下一位,最后再还原 为初始状态。贴一下代码,下面的代码也是一个模板!


import java.util.*;

public class lk {
	static Set<String> set = new HashSet<>(); //hash去重

	public static void main(String[] args) {
		String str = "ABCD";
		boolean[] used = new boolean[str.length()];
		dfs(str, used, "");
		for (String strs : set) {
			System.out.println(strs);
		}
	}

	private static void dfs(String str, boolean[] used, String string) {
		// TODO Auto-generated method stub
		if (string.length() == str.length()) { //终止条件
			set.add(string);
			return;
		}
		for (int i = 0; i < str.length(); i++) {
			if (used[i]) {
				continue;
			} else {
				used[i] = true;
				dfs(str, used, string+str.charAt(i) );
				used[i] = false; //回溯
			}
		}

	}
}

  • 算法
    353 引用 • 242 回帖 • 17 关注

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...