Welcome to Subscribe On Youtube

784. Letter Case Permutation

Description

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

 

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

 

Constraints:

• 1 <= s.length <= 12
• s consists of lowercase English letters, uppercase English letters, and digits.

Solutions

DFS.

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

• 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);
          }
      }
  }
  

• class Solution {
  public:
      vector<string> letterCasePermutation(string s) {
          vector<string> ans;
          function<void(int)> dfs = [&](int i) {
              if (i >= s.size()) {
                  ans.emplace_back(s);
                  return;
              }
              dfs(i + 1);
              if (s[i] >= 'A') {
                  s[i] ^= 32;
                  dfs(i + 1);
              }
          };
          dfs(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
  
  

• 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