CODEWITHSUNDEEP
python
kang
kang

Reputation: 707

Combinations of a String

The following was a job interview question which I struggled with. (Unnecessary switching between list and set, tested it and realised it was missing an expected output, too many steps). If possible, looking for the proper answer or maybe a guide on how I should have tackled the problem. Thank you.

Question: Give a String, find all possible combinations from it (Front and Reverse). Print all combinations and total count of combinations. Order doesn't matter.

Example s = 'polo'

Front Answer = 'p', 'po', 'pol', 'polo', 'ol', 'olo', 'lo', 'o', 'l'.
Reverse Answer: 'o', 'ol', 'olo', 'olop', 'lop', 'op', 'p', 'l'.

My answer:

count = 0
count2 = -1
length = len(s)
my_list = []
for i in s:
    temp = s[count:]
    temp2 = s[:count2]
    my_list.append(i)
    my_list.append(temp)
    my_list.append(temp2)
    count += 1
    count2 -= 1

my_set = set(my_list) 
for f in my_set:
    print(f)
print(len(my_set)) # Answer for front

new_list = []
for f in my_set:
    new_list.append(f[::-1])

print('Reverse Result:')
for f in new_list:
    print(f)
print(len(new_list)) # Answer for reverse

Upvotes: 3

Views: 117

Answers (2)

Js doe
Js doe

Reputation: 26

Try this:

   string = "polo"
   x = [string[i:j] for i in range(len(string)) for j in range(len(string),0,-1) if j > i ]
   x.sort()
   print("Forward:",x[::-1])
   print("Reverse:",x[::])

Upvotes: 0

Joe Iddon
Joe Iddon

Reputation: 20414

You can do this with two nested for-loops. One will loop through the start indexes and the nested one loops through the end indexes (starting from the start + 1 going to the length of s +1 to reach the very end).

With these two indexes (start and end), we can use string slicing to append that combination to the list forward. This gives you all the combinations as you see below.

To get the reversed ones, you could do a for-loop as you have done reversing the order of the forward ones, but to save the space, in the code below, we just append the same index but sliced from the reversed s (olop).

s = "polo"

forward = []
backward = []
for start in range(len(s)):
    for end in range(start+1, len(s)+1):
        forward.append(s[start:end])
        backward.append(s[::-1][start:end])

print(forward)
print(backward)
print(len(forward) + len(backward))

which outputs:

['p', 'po', 'pol', 'polo', 'o', 'ol', 'olo', 'l', 'lo', 'o']
['o', 'ol', 'olo', 'olop', 'l', 'lo', 'lop', 'o', 'op', 'p']
20

If you really wanted to make the code clean and short, you could do the same thing in a list-comprehension. The logic remains the same, but we just compress it down to 1 line:

s = "polo"

forward = [s[start:end] for start in range(len(s)) for end in range(start+1, len(s)+1)]    
backward = [c[::-1] for c in forward]

print(forward)
print(backward)
print(len(forward) + len(backward))

which gives the same output as before.

Hope this helps!

Upvotes: 2

Related Questions