Letter Case Permutations
Problem
The word has lowercase letters and digits. Change the case of any letters to get all different words. Print every word on its own line. Walk the letters from left to right, and for each letter print the lowercase choice first and then the uppercase choice (so the first all-lowercase word comes first).
Constraints
- 1 <= length <= 12
- lowercase letters and digits
Examples
Input
a1b2
Output
a1b2 a1B2 A1b2 A1B2
Solutions
At each letter we try both cases and go deeper. At the end of the word we save the result. With m letters there are 2^m words.
/*
* Problem : Case permutations.
* Input : One word.
* Output : All words, one per line.
* Approach: Backtracking.
* Time : O(2^m * n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
private static void walk(char[] letters, int position, java.util.List<String> out) {
if (position == letters.length) {
out.add(new String(letters));
return;
}
if (Character.isLetter(letters[position])) {
letters[position] = Character.toLowerCase(letters[position]);
walk(letters, position + 1, out);
letters[position] = Character.toUpperCase(letters[position]);
walk(letters, position + 1, out);
} else {
walk(letters, position + 1, out);
}
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String s) {
// Step 1: Walk the letters left to right. A letter gives two branches (lowercase first). A digit gives one branch.
java.util.List<String> out = new java.util.ArrayList<String>();
walk(s.toCharArray(), 0, out);
return out.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(String.join("\n", solve(s)));
}
}
Hints (2)
- What does a digit do to the branching?
- When do we save a word?