Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/784.html

Level

Easy

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.

Solution

First obtain all the indices where the character is a letter. Next obtain all possible permutations using the idea of binary numbers, and for each permutation, set the letters to lowercase and uppercase accordingly, and add the string to the result list.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 
  public class Letter_Case_Permutation {
      class Solution {
  
          public List<String> letterCasePermutation(String S) {
              if (S == null) {
                  return new LinkedList<>();
              }
  
              List<String> res = new LinkedList<>();
              helper(S.toCharArray(), res, 0);
              return res;
          }
  
          public void helper(char[] chs, List<String> res, int pos) {
              if (pos == chs.length) {
                  res.add(new String(chs));
                  return;
              }
              if (chs[pos] >= '0' && chs[pos] <= '9') {
                  helper(chs, res, pos + 1);
                  return;
              }
  
              chs[pos] = Character.toLowerCase(chs[pos]);
              helper(chs, res, pos + 1);
  
              chs[pos] = Character.toUpperCase(chs[pos]);
              helper(chs, res, pos + 1);
          }
      }
  }
  
  ############
  
  class Solution {
      private List<String> ans = new ArrayList<>();
      private char[] t;
  
      public List<String> letterCasePermutation(String s) {
          t = s.toCharArray();
          dfs(0);
          return ans;
      }
  
      private void dfs(int i) {
          if (i >= t.length) {
              ans.add(String.valueOf(t));
              return;
          }
          dfs(i + 1);
          if (t[i] >= 'A') {
              t[i] ^= 32;
              dfs(i + 1);
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/letter-case-permutation/
  // Time: O(2^N)
  // Space: O(N)
  class Solution {
  private:
      vector<string> ans;
      void dfs(string &S, int i) {
          while (i < S.size() && !isalpha(S[i])) ++i;
          if (i == S.size()) {
              ans.push_back(S);
              return;
          }
          dfs(S, i + 1);
          S[i] += ('A' - 'a') * ((S[i] >= 'a' && S[i] <= 'z') ? 1 : -1);
          dfs(S, i + 1);
      }
  public:
      vector<string> letterCasePermutation(string S) {
          dfs(S, 0);
          return ans;
      }
  };
  

• class Solution:
      def letterCasePermutation(self, s: str) -> List[str]:
          def dfs(i):
              if i >= len(s):
                  ans.append(''.join(t))
                  return
              dfs(i + 1)
              if t[i].isalpha():
                  t[i] = chr(ord(t[i]) ^ 32)
                  dfs(i + 1)
  
          t = list(s)
          ans = []
          dfs(0)
          return ans
  
  ############
  
  class Solution(object):
      def letterCasePermutation(self, S):
          """
          :type S: str
          :rtype: List[str]
          """
          res = []
          self.dfs(S, 0, res, '')
          return res
      
      def dfs(self, string, index, res, path):
          if index == len(string):
              res.append(path)
              return
          else:
              if string[index].isalpha():
                  self.dfs(string, index + 1, res, path + string[index].upper())
                  self.dfs(string, index + 1, res, path + string[index].lower())
              else:
                  self.dfs(string, index + 1, res, path + string[index])
  

• func letterCasePermutation(s string) (ans []string) {
  	t := []byte(s)
  	var dfs func(int)
  	dfs = func(i int) {
  		if i >= len(t) {
  			ans = append(ans, string(t))
  			return
  		}
  		dfs(i + 1)
  		if t[i] >= 'A' {
  			t[i] ^= 32
  			dfs(i + 1)
  		}
  	}
  
  	dfs(0)
  	return ans
  }
  

• function letterCasePermutation(s: string): string[] {
      const n = s.length;
      const cs = [...s];
      const res = [];
      const dfs = (i: number) => {
          if (i === n) {
              res.push(cs.join(''));
              return;
          }
          dfs(i + 1);
          if (cs[i] >= 'A') {
              cs[i] = String.fromCharCode(cs[i].charCodeAt(0) ^ 32);
              dfs(i + 1);
          }
      };
      dfs(0);
      return res;
  }
  
  

• impl Solution {
      fn dfs(i: usize, cs: &mut Vec<char>, res: &mut Vec<String>) {
          if i == cs.len() {
              res.push(cs.iter().collect());
              return;
          }
          Self::dfs(i + 1, cs, res);
          if cs[i] >= 'A' {
              cs[i] = char::from((cs[i] as u8) ^ 32);
              Self::dfs(i + 1, cs, res);
          }
      }
  
      pub fn letter_case_permutation(s: String) -> Vec<String> {
          let mut res = Vec::new();
          let mut cs = s.chars().collect::<Vec<char>>();
          Self::dfs(0, &mut cs, &mut res);
          res
      }
  }
  
  

All Problems

All Solutions