@@ -0,0 +1,1687 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * 784. Letter Case Permutation%0A * %3Cp%3E%0A * Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.%0A * Return a list of all possible strings we could create.%0A * %3Cp%3E%0A * Examples:%0A * Input: S = %22a1b2%22%0A * Output: %5B%22a1b2%22, %22a1B2%22, %22A1b2%22, %22A1B2%22%5D%0A * %3Cp%3E%0A * Input: S = %223z4%22%0A * Output: %5B%223z4%22, %223Z4%22%5D%0A * %3Cp%3E%0A * Input: S = %2212345%22%0A * Output: %5B%2212345%22%5D%0A * Note:%0A * %3Cp%3E%0A * S will be a string with length at most 12.%0A * S will consist only of letters or digits.%0A * %3Cp%3E%0A * Related Topics: Backtracking, Bit Manipulation%0A * Similar Questions: (M) Subsets%0A */%0Apublic class LetterCasePermutation %7B%0A%0A    /**%0A     * Backtracking%0A     * Since S is alphanumerical, numbers can be skipped and only check letters.%0A     * To generate all possible strings, all possibilities must be searched.%0A     * How? By backtracking with the letter itself and its opposite case.%0A     */%0A    public List%3CString%3E letterCasePermutation(String S) %7B%0A        List%3CString%3E res = new ArrayList%3C%3E();%0A        dfs(S.toCharArray(), 0, res);%0A        return res;%0A    %7D%0A%0A    private void dfs(char%5B%5D s, int pos, List%3CString%3E res) %7B%0A        if (pos == s.length) %7B%0A            res.add(new String(s));%0A            return;%0A        %7D%0A        dfs(s, pos + 1, res); // If it's a number or a letter, just recurse on.%0A        if (Character.isLetter(s%5Bpos%5D)) %7B // If it's a letter, recurse the other case.%0A            s%5Bpos%5D %5E= 1 %3C%3C 5; // Only the 6th significant bit is different of different cases.%0A            dfs(s, pos + 1, res);%0A            s%5Bpos%5D %5E= 1 %3C%3C 5;%0A        %7D%0A    %7D%0A%7D

add 784. Letter Case Permutation