Breakdown nested for loops in Python list comprehension that involves string concatenation

Question

I am trying to debug the nested for loop via Pycharm debugger... In the process of troubleshooting, I wanted to breakdown the loop into two individual loops and step through the code but I am having a hard time with this...

Here is the code block with list comprehension:

def letterCasePermutation(S):
    res = ['']
    for ch in S:
        if ch.isalpha():
            res = [i + j for i in res for j in [ch.upper(), ch.lower()]]
    return res

result = letterCasePermutation("ab")
print(result) # expected result = ['AB', 'Ab', 'aB', 'ab']

In order to debug this code block I would like to break down the list comprehension to something like this:

def letterCasePermutation(S):
    res = ['']
    for ch in S:
        if ch.isalpha():
            # res = [i + j for i in res for j in [ch.upper(), ch.lower()]]

            for i in res:
                for j in [ch.upper(), ch.lower()]:
                    res.append(i + j)
    return res

result = letterCasePermutation("ab")
print(result)

The above block results in an infinite loop error instead of providing the result like code block-1. expected result = ['AB', 'Ab', 'aB', 'ab']

I am not able to figure what I am missing. After spending considerable amount of time and still being stuck, I decided to post this question. Thanks for the help in advance.

Siddhant · Accepted Answer · 2019-10-16T02:27:37.400

It results in an infinite loop because you are iterating on res, for i in res, and appending new values in it at the same time res.append(i + j).

Which is not the case with list-comprehension since expression on the right of = is evaluated and assigned to res.

You can use a second list to avoid doing that like so,

def letterCasePermutation(S):
res = ['']
for ch in S:
    if ch.isalpha():
        _res = []
        for i in res:
            for j in [ch.upper(), ch.lower()]:
                _res.append(i + j)
        res = res + _res
return res

result = letterCasePermutation("ab")
print(result)

Edit:

def letterCasePermutation(S):
res = ['']
for ch in S:
    if ch.isalpha():
        _res = []
        for i in res:
            for j in [ch.upper(), ch.lower()]:
                _res.append(i + j)
        res = _res
return res
result = letterCasePermutation("ab")
print(result)

Thank you @Siddhant for taking the time to answer the question. What still puzzles me is while returning the result how can I dynamically splice ? I tried playing around with the above code you posted and I get the result as ['', 'A', 'a', 'B', 'b', 'AB', 'Ab', 'aB', 'ab'] which is incorrect — InquisitiveGirl, Oct 16 '19 at 00:58

score 1 · Answer 2 · answered Oct 15 '19 at 03:28

Comprehensions don't care about assinging to the same name as used in the comprehension.

a = [0, 1, 2, 3, 4]
a = [i*2 for i in a]
print(a)

Outputs [0, 2, 4, 6, 8].

With your example you are adding elements to the res list while iterating over it:

for i in a:
    a.append(i)

This gives you an infinite loop because as you proceed to the next element, more elements are added to the list.

Your options are either assigning to a new variable name, or using slicing to iterate over a temporary copy of the list:

a = [0, 1, 2, 3, 4]
b = []
for i in a:
    b.append(i)

print(b)

Outputs [0, 1, 2, 3, 4]

a = [0, 1, 2, 3, 4]
for i in a[:]:
    a.append(i)

print(a)

Output is [0, 1, 2, 3, 4, 0, 1, 2, 3, 4].

a[:] is a slice of a from the first to the last element with a step of 1. You can read more about slicing here or in the official python docs.

score 0 · Answer 3 · answered Oct 16 '19 at 02:25

Here is the breakdown :) thank you both for helping me with the idea.

def letterCasePermutation(S):
    res = ['']
    for ch in S:
        _res = []
        for i in res:
            for j in [ch.upper(), ch.lower()]:
                _res.append(i + j)
        res = _res
    return res


result = letterCasePermutation("ab")
print(result)

Breakdown nested for loops in Python list comprehension that involves string concatenation

3 Answers3