Interview Bootcamp
Vote

0% completed

​

Solution: String Permutations by changing case

Problem Statement

Given a string, find all of its permutations preserving the character sequence but changing case.

Example 1:

Input: "ad52"
Output: "ad52", "Ad52", "aD52", "AD52"

Example 2:

Input: "ab7c"
Output: "ab7c", "Ab7c", "aB7c", "AB7c", "ab7C", "Ab7C", "aB7C", "AB7C"

Constraints:

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

Solution

This problem follows the Subsets pattern and can be mapped to Permutations.

.....

.....

.....

Like the course? Get enrolled and start learning!
K

k

· 3 years ago

Given Approach:

#convert string to list of characters

chs = list(string) # if the current char is in upper case, change it to lower case or vice versa chs[i] = chs[i].swapcase() string = ''.join(chs))

Suggested Approach:

  • This will be much faster execution
  • Quick to wirte.

string = string[:j] + string[j].swapcase() + string[j+1:]

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLetterCaseStringPermutations(self, text):
   
    def backtrack(word, result, seen, index):
      result.append(word[:])
      
      for i in range(index, len(word)): # loop through each character in the text
        char = word[i]
       
        if i not in seen and not char.isnumeric(): # if the character is not a number and have no been seen 
          seen.add(i)
          new_word = word[:i] + char.swapcase() + word[i + 1:]
          backtrack(new_word, result, seen, i) # recurse back 
        
          seen.remove(i)

    result = []
    backtrack(text, result, set(), 0)
    return result
Show 1 reply
A

Athanasios Petsas

· 5 years ago

In C++ sollution, we don't need to transform the string to an array of chars for doing the upper/lower case change and then transform it back to add it to the result vector; we can just do it in place. Here's the code having this change:

{code} static vector findLetterCaseStringPermutations(const string& str) { vector permutations; if (str == "") { return permutations; }

permutations.push_back(str); // process every character of the string one by one for (int i = 0; i < str.length(); i++) { if (!isalpha(str[i])) // only process characters, skip digits continue; // we'll take all existing permutations and change the letter case appropriately int n = permutations.size(); for (int j = 0; j < n; j++) { string newPerm = permutations[j]; // if the current char is in upper case change it to lo

T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def findLetterCaseStringPermutations(self, str):
    permutations = []
    # TODO: Write your code here
    #[a,b,c]
    #[a][A]
    #[ab][aB][Ab][AB]
    #[abc][abC][aBc][aBC][Abc][AbC][ABc][ABC]
    # so loop through string, if char is number just append to all queue items
    # for char is number, append it with 2 cases: lowercase and uppercase
    curr_queue = deque()
    curr_queue.append("")
    for character in str:
      curr_queue_length = len(curr_queue)
      for _ in range(curr_queue_length):
        curr_str = curr_queue.popleft()
        if character.isdigit():
          curr_str += character
          if(len(curr_str) >= len(str)):
            permutations.append(curr_str)
          else:
            curr_queue.ap
T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def findLetterCaseStringPermutations(self, str):
    permutations = []
    # TODO: Write your code here
    #[a,b,c]
    #[a][A]
    #[ab][aB][Ab][AB]
    #[abc][abC][aBc][aBC][Abc][AbC][ABc][ABC]
    # so loop through string, if char is number just append to all queue items
    # for char is number, append it with 2 cases: lowercase and uppercase
    curr_queue = deque()
    curr_queue.append("")
    for character in str:
      curr_queue_length = len(curr_queue)
      for _ in range(curr_queue_length):
        curr_str = curr_queue.popleft()
        if character.isdigit():
          curr_str += character
          if(len(curr_str) >= len(str)):
            permutations.append(curr_str)
          else:
            curr_queue.ap
Debasis B

Debasis B

· 2 years ago

    // List to store all permutations
    List<string> permutations = new List<string>();
    
    public List<string> findLetterCaseStringPermutations(string str)
    {
        // Begin the process
        find(currPermutation: str.ToCharArray(), index: 0);
        return permutations;
    }
    
    private void find(char[] currPermutation, int index)
    {
        // Base case: if index is out of bounds, add the current permutation to the list
        if (index == currPermutation.Length)
        {
            permutations.Add(string.Concat(currPermutation));
            return;
        }

        // If character is letter, toggle case and find next permutation 
        if (char.IsLetter(currPermutation[index]))
        {
            // Toggle case for the character at the
Viktor Pokazanyev

Viktor Pokazanyev

· 7 months ago

class Solution:
  def _permute(self, s, idx, cur_res, result):
    if idx == len(s):
      result.append(cur_res)
    else:
      if s[idx].isalpha():
        self._permute(s, idx + 1, cur_res + s[idx].swapcase(), result)
      self._permute(s, idx + 1, cur_res + s[idx], result)

  def findLetterCaseStringPermutations(self, str):
    permutations = []
    self._permute(str, 0, '', permutations)
    return permutations