All permutations of a string

Write a method to compute all permutations of a string.

My initial thoughts:

  • Base case: the string is a single character, the only permutation is itself.
  • Recursion: all permutations of size n can be obtained by insert the first character S[0] into all the possible positions of permutations of size n-1.

My initial codes:

	public static Set<String> allPermutationsOfString(String s) {
		if (s.length() == 1) {
			Set<String> result = new HashSet<String>();
			result.add(s);
			return result;
		} else {
			Set<String> result = new HashSet<String>();
			char c = s.charAt(0);
			Set<String> subPermutations = allPermutationsOfString(s
					.substring(1));
			for (String permutation : subPermutations) {
				// String newPermutation = new String();
				for (int i = 0; i < permutation.length(); ++i) {
					String newPermutation = permutation.substring(0, i) + c
							+ permutation.substring(i);
					result.add(newPermutation);
				}
			}
			return result;
		}
	}

Comments after running:
It doesn’t work as expected.

  • INPUT: “abc”
  • EXPECTED OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba”
  • ACTUAL OUTPUT: “abc”, “bac”
  • CORRECTION: The highlighted line 13 should be revised to:
    				for (int i = 0; i <= permutation.length(); ++i) {
    

Solution:

	public static ArrayList<String> getPerms(String s) {
		ArrayList<String> permutations = new ArrayList<String>();
		if (s == null) { // error case
			return null;
		} else if (s.length() == 0) { // base case
			permutations.add("");
			return permutations;
		}
		char first = s.charAt(0); // get the first character
		String remainder = s.substring(1); // remove the first character
		ArrayList<String> words = getPerms(remainder);
		for (String word : words) {
			for (int j = 0; j <= word.length(); j++) {
				permutations.add(insertCharAt(word, first, j));
			}
		}
		return permutations;
	}

	public static String insertCharAt(String word, char c, int i) {
		String start = word.substring(0, i);
		String end = word.substring(i);
		return start + c + end;
	}

Comments: exactly the same as mine except that it handles error case where string is null.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: