CODEWITHSUNDEEP
python
Praful Bagai
Praful Bagai

Reputation: 17382

Algorithmic string in python?

I have a string say a = "awxxxyyw".

It should remove all the consecutive elements from the string and return me final string as "a".

ie in 1st iteration xxx seems to be consecutive, so remove xxx, then string becomes awyyw.

2nd iteration removes yy. string becomes aww.

3rd iteration remove ww. returns a

Here is my code.

Where I'm going wrong?

def func(string,pointer):
    print pointer

    for i in range(pointer,len(string)):
        flag=0
        temp = i
        print temp,pointer
        try:
            while(string[i-1] == string[i]):
                print string
                i+= 1
                flag = 1
        except : break

        if flag == 0 :
            continue

        else:
            string = string[0:temp] + string[i+1:len(string)]
            func(string, temp)

    return string


string = "awxxxyyw"
print func(string,1)

Upvotes: 1

Views: 88

Answers (5)

Tim Peters
Tim Peters

Reputation: 70602

I think this is easiest to do with an iterated regular expression substitution:

def remove_dups(s):
    import re
    pat = re.compile(r"(.)\1+")
    while True:
        news = pat.sub("", s)
        if s == news:
            break
        s = news
    return s

print remove_dups("awxxxyyw") # "a"
print remove_dups("aaxyyza")  # "xza"

Upvotes: 3

jonrsharpe
jonrsharpe

Reputation: 122052

You need to modify your code to remove all consecutive repeated letters, rather than one at a time. Retaining your recursion:

def func(string):
    for i in range(len(string) - 1):
        if string[i] == string[i+1]:
            j = i + 1
            while j < len(string) and string[j] == string[i]:
                j += 1
            return func(string[:i] + string[j:])
    return string

Upvotes: 1

Maciej Gol
Maciej Gol

Reputation: 15854

A working demo:

def func(s):
    stack = ['']
    idx = 0

    while idx < len(s):
        if s[idx] == stack[-1]:
            el = s[idx]
            stack.pop()
            while idx < len(s) and s[idx] == el:
                idx += 1
        else:
            stack.append(s[idx])
            idx += 1
    return ''.join(stack)

print func('awxxxyyw')
'a'
print func('awxyw')
'awxyw'
print func('a')
'a'
print func('abcdefghijklmnoprstuvxywzzwyxvutsrponmlkjihgfedcba')
''

Upvotes: 1

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 250971

You can do this using itertools.groupby, it allows you to group adjacent similar items:

from itertools import groupby

def solve(x):
    while True:
        lis = [list(g) for k, g in groupby(x)]
        print lis
        #if any item in lis has length != 1 then remove all such items
        if any(len(x) != 1 for x in lis):
           x = ''.join([''.join(x) for x in lis if len(x)==1])
        else:
            return ''.join([''.join(x) for x in lis])


s = "awxxxyyw"
print solve(s)
print 
s = 'aaacccxxxka'
print solve(s)

Output:

[['a'], ['w'], ['x', 'x', 'x'], ['y', 'y'], ['w']] #remove ['x', 'x', 'x'], ['y', 'y'] here
[['a'], ['w', 'w']]           #remove ['w', 'w'] here
[['a']]                       #nothing to remove, returns this as answer.
a

[['a', 'a', 'a'], ['c', 'c', 'c'], ['x', 'x', 'x'], ['k'], ['a']]
[['k'], ['a']]
ka

Upvotes: 1

bdesham
bdesham

Reputation: 16089

The problem with your code is that you’re only ever removing one character at a time, and so repeated sequences will be reduced to a single character, but that single character will stick around at the end. For example, your code goes from “xxx” to “xx” to “x”, but since there’s only a single “x” left that “x” is not removed from the string. Adapt your code to remove all of the consecutive repeated characters and your problem will be fixed.

Upvotes: 3

Related Questions