Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1369
Question Name: String Permutation
Question Description: Give a string, use all the letters of that string to construct all distinct permutations.
Input: the input might contain multiple test cases. Each line contains a string as a test case. All tests have length less than 10. And they may contain duplicate letters.
Output: For each test case, print all the distinct permutations in lexicographical order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Input: abc BCA Output: abc acb bac bca cab cba ABC ACB BAC BCA CAB CBA |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/24/2014 * Last updated: 08/24/2014 * * Filename: StringPermutation.java * Compilation: javac StringPermutation.java * Execution: java StringPermutation * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; /** * A utility to print all the permutations of a give string lexicographically. * @author Sheng Yu codesays.com */ public class StringPermutation { /** * Sterilize the give string. Remove the duplicate elements and sort it. * @param original the string to be sterilized. * @return the sterilized string. */ public String getSortedDistinct(String original) { // No need to clear the original string. if (original.length() < 2) return original; // Sort the original string. char[] sorted = original.toCharArray(); Arrays.sort(sorted); // Remove the duplicate item in the sorted string. StringBuilder sortedAndDistinct = new StringBuilder(); sortedAndDistinct.append(sorted[0]); for (int i = 1; i < sorted.length; ++i) { if (sorted[i] == sorted[i-1]) continue; else sortedAndDistinct.append(sorted[i]); } return sortedAndDistinct.toString(); } /** * Get the occurrence of each letter in original string. The result, to say * occurrence[], is corresponding to the input cleared. In other words, * occurrence[i] = j means cleared[i] appears j times in original string. * @param original the original string to count occurrence. * @param cleared the sorted and distinct letters in original string. * @return the occurrence of each cleared letter in original string. */ public int[] getOccurrence(String original, char[] cleared) { int[] occurrence = new int[cleared.length]; // Get the occurrence. Map<Character, Integer> unordered = new HashMap<Character, Integer>(); for (char letter : original.toCharArray()) { if (unordered.get(letter) == null) { unordered.put(letter, 1); } else { unordered.put(letter, unordered.get(letter) + 1); } } // Store the occurrence according to the cleared array. for (int i = 0; i < occurrence.length; ++i) { occurrence[i] = unordered.get(cleared[i]); } return occurrence; } /** * Show all permutations of candidates. * @param intermediate the filled part of one permutation. * @param pos the position in intermediate to fill the next letter. * @param candidate the candidates to use to generate the permutation. * @param used indicates which candidates have been used in generating * permutation. * @param output the cache for output, to improve the performance only. */ public void showPermutation(char[] intermediate, int pos, char[] candidate, int[] occurrence, StringBuilder output) { if (pos == intermediate.length) { // Get one permutation. output.append(intermediate); output.append("n"); } else { // Try to append every unused letter. for (int i = 0; i < candidate.length; ++i) { if (occurrence[i] > 0) { occurrence[i] -= 1; intermediate[pos] = candidate[i]; showPermutation(intermediate, pos + 1, candidate, occurrence, output); occurrence[i] += 1; } } } return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String original = null; char[] cleared = null; int[] occurrence = null; char[] intermediaeStatus = null; StringBuilder sb = new StringBuilder(); StringPermutation itertool = new StringPermutation(); while (scanner.hasNextLine()) { original = scanner.nextLine(); // Sterilize the original input. cleared = itertool.getSortedDistinct(original).toCharArray(); // Get the occurrence of each letter. occurrence = itertool.getOccurrence(original, cleared); // Show all the string permutation. intermediaeStatus = new char[original.length()]; itertool.showPermutation(intermediaeStatus, 0, cleared, occurrence, sb); System.out.print(sb); // Clear the context for next test case. sb.delete(0, sb.length()); intermediaeStatus = null; } scanner.close(); } } |