Letter case permutation

Question

The question can be found here https://leetcode.com/problems/letter-case-permutation

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.

My question pertains mostly to the pattern that I am following. I find that with alot of these leetcode question that I want to use recursion for I find myself making two versions of a function. One which acts as the "interface" is this case letterCasePermutation and one which acts as the worker (letterCasePermutationAux) where the only difference is the arguments (I would usually have something like a counter and a reference to a vector to hold my answers).

I choose this question as an example but really any recursive question could act as a stand in here.

class Solution(object):

    ans = []

    def letterCasePermutationAux(self, S, i=0):

        if i >= len(S):
            self.ans.append(S)
            return

        if S[i].isalpha():
            temp = list(S)
            temp[i] = S[i].upper() if S[i].islower() else S[i].lower()
            self.letterCasePermutationAux("".join(temp), i+1)

        self.letterCasePermutationAux(S,i+1)


    def letterCasePermutation(self, S):
        self.ans=[]
        self.letterCasePermutationAux(S)
        return self.ans

My question is, is there a nicer way I can go about accomplishing this task? One which can perform recursion only using one function?

Answer 1

It's fairly common to use an auxiliary parameter as an index or accumulator in recursive functions. If you don't like having the extra function or method "cluttering" the namespace, you can nest it inside the driver like this:

class Solution:

    def letterCasePermutation(self, S):

        def aux(S, i):

            if i >= len(S) and len(S) > 0:
                self.ans.append(S)
                return

            if S[i].isalpha():
                temp = list(S)
                temp[i] = S[i].upper() if S[i].islower() else S[i].lower()
                self.letterCasePermutationAux("".join(temp), i+1)

            self.letterCasePermutationAux(S,i+1)

        self.ans=[]
        self.letterCasePermutationAux(S)

        return self.ans

A common way to recursively process a string, list, or other sequence is to define the base case as an empty sequence which returns a list with with the base case answer. If the sequence isn't empty, take off the first element of the sequence and recursively call the function with the rest of the list. Then process the list returned by the recursive call to add back in the first element.

class Solution:
    def letterCasePermutation(self, s):

        # base case the answer is a list with an empty string
        if s == '':
            return ['']

        else:
            ans = []

            if s[0].isalpha():    
                # if s[0] is a letter, prepend it to all the answers in the list
                # returned by the recursive call.  First as a lowercase letter
                # and then as an uppercase letter
                for tail in self.letterCasePermutation(s[1:]):
                    ans.append(s[0].lower() + tail)
                    ans.append(s[0].upper() + tail)

            else:
                # if it's not a letter, just prepend it to all the answers in 
                # the list returned by the recursive call.
                for tail in self.letterCasePermutation(s[1:]):
                    ans.append(s[0] + tail)

            return ans

Here's an elegant solution using generators to create the permutations lazily:

class Solution:

    def letterCasePermutation(self, s):
        def aux(s, acc):
            if s == '':
                yield acc

            else:
                yield from aux(s[1:], acc + s[0])

                if s[0].isalpha():
                    yield from aux(s[1:], acc + s[0].swapcase())

        yield from  aux(s, '')

Answer 2

Solving without Recursion

Here is a very simple way to solve this specific problem without recursion and with only a single function. It might not extend to all the similar problems you want to, but it could extend to some of them:

def letterCasePermutation(S):
    results = [S]
    for i, char in enumerate(S):
        if char.isalpha():
            new_char = char.upper() if char.islower() else char.lower()
            results += [''.join([result[:i], new_char, result[i+1:]]) for result in results]
    return results

The idea is that each time we change a character, we can construct a new result for each old result, by simply slicing in the changed character on all those new results.

Recursion with Decorator

If the structure of the outer function is simple (or you are through enough in how you write your decorator) then we can write a simple decorator for such functions to use. The one to use here will be one lazily constructing parameters.

Decorator based on reference

If want to keep the format of your solution (the recursive function is side effect only), then we need to have the decorator specifically know that parameter and return it as a result. Your solution (taken as a function instead of as a method) with this method applied to it:

def lazy_curry_by_ref(results=list,**other_params):
    def dec(f):
        def wrapped(*args,**kwargs):
            result_item = results()
            other_params_items = {param:other_params[param]() for param in other_params}
            f(*args, **kwargs, result=result_item, **other_params_items, call_self=f)
            return result_item
        return wrapped
    return dec

@lazy_curry_by_ref(results=list,i=int)
def letterCasePermutation(self, S, i=0, results=None, call_self=None):

    if i >= len(S):
        results.append(S)
        return

    if S[i].isalpha():
        temp = list(S)
        temp[i] = S[i].upper() if S[i].islower() else S[i].lower()
        call_self("".join(temp), i+1, results)

    call_self(S, i+1, results)

Note that I have specifically not included the typical functools.wrap(f) decorator on the inner decorator, since the the signature have changed and cannot be used anymore, so one would need to write a different type of decorator or special code to handle this.

Decoratur based on return

The above solution would be even simpler if we rewrote the program to return results, then we could just use a classic lazy_curry decorator:

def lazy_curry(**params):
    def dec(f):
        def wrapped(*args,**kwargs):
            params_items = {param:params[param]() for param in params}
            return f(*args,**kwargs, **params_items, call_self=f)
        return wrapped
    return dec

@lazy_curry(results=list,i=int)
def letterCasePermutation(self, S, i=0, results=None, call_self=None):

    if i >= len(S):
        results.append(S)
        return results

    if S[i].isalpha():
        temp = list(S)
        temp[i] = S[i].upper() if S[i].islower() else S[i].lower()
        call_self("".join(temp), i+1, results)

    return call_self(S, i+1, results)