Algorithmic string in python?

Question

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)

Can someone please rectify the code or can provide a new code. Thanks — Praful Bagai
– Praful Bagai, Commented Dec 2, 2013 at 17:31
I've compiled it and what I'm getting is awxyw. How can I make it according to my needs? — Praful Bagai
– Praful Bagai, Commented Dec 2, 2013 at 17:35
When asking for help, make sure you include as part of the question (not the comments) what output you are currently seeing and the output you expect, based on your given input. — SethMMorton
– SethMMorton, Commented Dec 2, 2013 at 17:41

bdesham · Accepted Answer · 2013-12-02 17:34:10Z

3

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.

answered Dec 2, 2013 at 17:34

bdesham

16.3k15 gold badges88 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Praful Bagai Over a year ago

Well I've tried to splice the string accordingly, but that doesn't work. Can you please provide a working demo. Thanks

Tim Peters · Accepted Answer · 2013-12-02 17:47:02Z

3

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"

answered Dec 2, 2013 at 17:47

Tim Peters

71.4k14 gold badges133 silver badges140 bronze badges

2 Comments

Joran Beasley Over a year ago

I was just about to put while s != re.sub("(.)\\1+","",s): s = re.sub("(.)\\1+","",s) :) but yours is better since it uses a compiled regex

Tim Peters Over a year ago

Eh, most versions of Python maintain an internal cache of recently-compiled regexps, so it shouldn't matter much. I just like compiling regexps in their own step :-)

jonrsharpe · Accepted Answer · 2013-12-02 17:46:34Z

1

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

answered Dec 2, 2013 at 17:46

jonrsharpe

123k31 gold badges277 silver badges488 bronze badges

Comments

Ashwini Chaudhary · Accepted Answer · 2013-12-02 17:43:21Z

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

Maciej Gol · Accepted Answer · 2013-12-02 17:44:03Z

1

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')
''

answered Dec 2, 2013 at 17:44

Maciej Gol

15.9k4 gold badges35 silver badges52 bronze badges

Collectives™ on Stack Overflow

Algorithmic string in python?

5 Answers 5

1 Comment

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related