[Algo Rhythm🕺💃] LeetCode 784. Letter Case Permutation

📚 Problem description

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.

 

🎯 My code

class Solution {
    public List<String> letterCasePermutation(String S) {
        char[] arr = S.toCharArray();
        List<String> answer = new ArrayList<>();
        
        backtracking(arr, answer, 0);
        
        return answer;
    }
    
    public void backtracking(char[] arr, List<String> answer, int idx) {
        if(idx == arr.length) {
            answer.add(new String(arr));
            return;
        }
        
        char c = arr[idx];
        if(Character.isLetter(c)) {
            arr[idx] = Character.toLowerCase(c);
            backtracking(arr, answer, idx + 1);
            arr[idx] = Character.toUpperCase(c);
            backtracking(arr, answer, idx + 1);
        }
        else {
            backtracking(arr, answer, idx + 1);
        }
    }
}

 

🧐 Why I wrote that code

It was a typical example of backtracking problem.

I divided a branch into two, one for lower case, the other for upper case, only when the character on focused index is letter.

Below is an example.

 

📖 What I learned

I learned that the essence of backtracking is 'branching only the promising child'.