Letter Case Permutation

LeetCode Q 784 - Letter Case Permutation

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2" ; Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4" ; Output: ["3z4", "3Z4"]

Input: S = "12345" ; Output: ["12345"]

Note:

• S will be a string with length between 1 and 12.
• S will consist only of letters or digits.

Solution :

Solution 1 : DFS / Backtracking

Code:

private List<List<Integer>> res;
public List<String> letterCasePermutation(String S) {
	res = new ArrayList<>();
	if (S == null || S.length == 0) return res;
	backtrack(S, 0, "");
	return res;
}

private void backtrack(String S, int pos, String curr) {
	if (pos == S.length()) {
		res.add(curr); return;
	}

	char ch = S.charAt(pos);
	if (Character.isLetter(ch)) {
		backtrack(S, pos + 1, curr + Character.toUpperCase(ch));
		backtrack(S, pos + 1, curr + Character.toLowerCase(ch));
	} else {
		backtrack(S, pos + 1, curr + ch);
	}
	
	return;
}

Solution 2 : BFS

Code:

public List<String> letterCasePermutation(String S) {

	if (S == null || S.length == 0) return new LinkedList<>();

	Queue<String> que= new LinkedList<>();
	que.offer(S);

	for (int i = 0; i < S.length(); i++) {

		if (Character.isDigit(S.charAt(i))) continue;

		int size = que.size();
		for (int i = 0; i < size; i++) {
			String str = que.poll();
			char[] chs = str.toCharArray();

			chs[i] = Character.toUpperCase(chs[i]);
			que.offer(String.valueOf(chs));
			chs[i] = Character.toLowerCase(chs[i]);
			que.offer(String.valueOf(chs));
		}
	}

	return new LinkedList<>(que);
}