Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: String Permutations by changing case

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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:]

A

Anonymous

· 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

Reading Progress

0%

Vote for new content