字符串-全排列

xiaoxiao2021-02-28  19

题目:输入一串字符,然后对字符进行全排列并打印。 如“abc”,全排列结果为:”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。 这是笔者经历的阿里一面的笔试题,折戟在此,是以为记。

参考:Java实现全排列、组合算法

分析: 1、从字符串中选择一个作为第一个字符,然后对剩下的字符串进行全排列; 2、核心内容就是置换; 3、打印放在递归的出口处进行; 4、要考虑去重。

Java代码实现:

HashSet<String> mHashSet = null; /** * 字符串的全排列 * * @param charSet */ public void startPerm(char[] charSet) { mHashSet = new HashSet(); perm(charSet, 0); mHashSet.clear(); } public void perm(char[] charSet, int from) { if (charSet == null || from >= charSet.length) { return; } if (from == charSet.length - 1) { /** 去重 start *******/ String key = String.valueOf(charSet); Iterator setIterator = mHashSet.iterator(); while (setIterator.hasNext()){ if(key.equals(setIterator.next())){ return; } } mHashSet.add(key); /** 去重 end *******/ System.out.println(charSet); return; } for (int i = from; i < charSet.length; i++) { swap(charSet, i, from); perm(charSet, from + 1); swap(charSet, i, from); } } public void swap(char[] charSet, int from, int to) { if (charSet == null || from >= charSet.length || to >= charSet.length) { return; } char temp = charSet[from]; charSet[from] = charSet[to]; charSet[to] = temp; }
转载请注明原文地址: https://www.6miu.com/read-1450227.html

最新回复(0)