Permute a string by changing case python

Question

Leetcode Backtracking Bit Manipulation

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.

Table of Contents Show

1. Recursive Implementation
2. Iterative Implementation
How do you Permutate a string in Python?
How do you change case in Python?
How do you find the possible combinations of a string in Python?
How do I print all the combinations of a string?

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.

分析¶

使用回溯法:

public List<String> letterCasePermutation(String S) {
    List<String> list = new ArrayList<>();
    if (S == null) return list;
    letterCasePermutation(list, new StringBuilder(), S, 0);
    return list;
}


private void letterCasePermutation(List<String> list, 
            StringBuilder sb, String S, int index){
    // base case
    if (index == S.length()) {list.add(sb.toString()); return;}
    // chosen
    char c = S.charAt(index);
    if (!Character.isLetter(c)) {  // numbers
        sb.append(c);
        letterCasePermutation(list, sb, S, index + 1);      // explore
        sb.deleteCharAt(sb.length() - 1);                   // unchosen
    } else {
        sb.append(Character.toLowerCase(c));
        letterCasePermutation(list, sb, S, index + 1);
        sb.deleteCharAt(sb.length() - 1);

        sb.append(Character.toUpperCase(c));
        letterCasePermutation(list, sb, S, index + 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}

In this post, we will see how to list out all permutations of a string in Python.

For example, the string ABC has 6 permutations, i.e., ABC, ACB, BAC, BCA, CBA, CAB.

Practice this problem

In Python, we can use the built-in module itertools to get permutations of elements in the list using the permutations() function.

import itertools

if__name__=='__main__':

s='ABC'

nums= list(s)

permutations= list(itertools.permutations(nums))

# Output: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

print([''.join(permutation) forpermutation inpermutations])

However, we can also write your utility function to generate all permutations of a string. We can do this either recursively or iteratively.

1. Recursive Implementation

The idea is to convert the given string to a character array, and in-place generate all its permutations using backtracking.

We can do this by swapping each of the remaining characters in the string with its first character and generating all the permutations of the remaining characters using a recursive call. This is illustrated in the recursion tree shown below.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# Function to swap two characters in a character array

defswap(ch,i, j):

temp=ch[i]

ch[i]=ch[j]

ch[j]=temp

# Recursive function to generate all permutations of a string

defpermutations(ch,curr_index=0):

ifcurr_index==len(ch) -1:

print(''.join(ch))

for iinrange(curr_index, len(ch)):

swap(ch,curr_index,i)

permutations(ch,curr_index+1)

swap(ch,curr_index,i)

if __name__=='__main__':

s='ABC'

permutations(list(s))

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Here’s another implementation in Python which doesn’t convert the string to a character array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Recursive function to generate all permutations of a string

defpermutations(remaining, candidate=''):

if len(remaining)==0:

print(candidate)

foriin range(len(remaining)):

newCandidate =candidate+remaining[i]

newRemaining=remaining[0:i]+ remaining[i+1:]

permutations(newRemaining,newCandidate)

if__name__ =='__main__':

s='ABC'

permutations(s)

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

2. Iterative Implementation

The idea is to store the partially generated permutations and then use those partial permutations to generate the final permutations in further iterations. Here’s how the code would look like:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

# Iterative function to generate all permutations of a string in Python

defpermutations(s):

# base case

ifnots:

return []

# create a list to store (partial) permutations

partial= []

# initialize the list with the first character of the string

partial.append(s[0])

# do for every character of the specified string

foriinrange(1, len(s)):

# consider previously constructed partial permutation one by one

# iterate backward

forjin reversed(range(len(partial))):

# remove the current partial permutation from the list

curr= partial.pop(j)

# Insert the next character of the specified string into all

# possible positions of current partial permutation.

# Then insert each of these newly constructed strings into the list

for kinrange(len(curr)+1):

partial.append(curr[:k]+ s[i]+curr[k:])

print(partial,end='')

if __name__=='__main__':

s='ABC'

permutations(s)

Download Run Code

Output:

[‘CAB’, ‘ACB’, ‘ABC’, ‘CBA’, ‘BCA’, ‘BAC’]

The time complexity of the above solutions is O(n.n!) since there are n! permutations for a string of length n, and each permutation takes O(n) time.

How do you Permutate a string in Python?

Procedure To Find The Permutation Of A String.

Import the itertools module..

Initialize the string..

Use the itertools. permutations method to find the permutation of the string..

In the third step, the method returns an object and convert it into a list. List contains a permutation of string as tuples..

How do you change case in Python?

In Python, upper() is a built-in method used for string handling. The upper() method returns the uppercased string from the given string. It converts all lowercase characters to uppercase. If no lowercase characters exist, it returns the original string.

How do you find the possible combinations of a string in Python?

To find all possible permutations of a given string, you can use the itertools module which has a useful method called permutations(iterable[, r]). This method return successive r length permutations of elements in the iterable as tuples.

How do I print all the combinations of a string?

Using a backtracking approach, all the permutations of the given string can be printed. Backtracking is an algorithm for finding all the possible solutions by exploring all possible ways.

kode python