1

I am trying to write a python program that will take any string of lowercase letters and return the longest alphabetical substring within it. Below is a segment of the code. 

s="abc"                                            #sample string
anslist=[]                                         #stores answers
shift=0                                            #shifts substring
expan=0                                            #expands substring
while len(s) >= 1+shift+expan:                     #within bounds of s
    if s[0+shift+expan] > s[1+shift+expan]:        #if not alphabetical
        shift += 1                                 #moves substring over
    else:                                          #if alphabetical
        while s[0+shift+expan] <= s[1+shift+expan]:  #while alphabetical
            expan += 1                               #checks next letter
        anslist += s[0+shift:2+shift+expan]       #adds substring to ans
        expan = 0                                  #resets expansion

When I run the code, the line containing while s[0+shift+expan] <= s[1+shift+expan]: creates an error that the string index is outside of the range. I see that adding to expan will put the index out of range, but shouldn't the largest while loop solve this? I appreciate any help.

4

2 回答 2

1

First, why your code doesn't work:

  • You aren't protecting your inner loop against running off the end of the string
  • your indexes are off when "saving" the substring
  • you += onto anslist, which is not how you add strings to a list
  • you don't increment the shift after processing a substring, so when it clears expan it starts over at the same index and loops forever

Fixed code (inline comments explain changes):

s="abckdefghacbde"                                 #sample string
anslist=[]                                         #stores answers
shift=0                                            #shifts substring
expan=0                                            #expands substring
while len(s) > 1+shift+expan:                      #within bounds of s
    if s[0+shift+expan] > s[1+shift+expan]:        #if not alphabetical
        shift += 1                                 #moves substring over
    else:                                          #if alphabetical
        # Added guard for end of string
        while len(s) > 1 + shift + expan and       # While still valid
              s[0+shift+expan] <= s[1+shift+expan]:# While alphabetical
            expan += 1                             #checks next letter
        # Fixed string sublength and append instead of +=
        anslist.append(s[0+shift:1+shift+expan])   #adds substring to ans
        # Continue to next possible substring
        shift += expan                             # skip inner substrings
        expan = 0  
print anslist

Results in:

['abck', 'defgh', 'ac', 'bde']

So the last step would be to find the one with the longest length, which I'll leave up to you, since this looks like homework.

To answer the question:

I see that adding to expan will put the index out of range, but shouldn't the largest while loop solve this?

It protects against your starting substring index from going off, but not your expansion. You must protect against both possibilities.

于 2017-06-08T20:08:57.277 回答
0

Have a look at this. 

>>> import re
>>> words = []
>>> word = r'[a]*[b]*[c]*[d]*[e]*[f]*[g]*[h]*[i]*[j]*[k]*[l]*[m]*[n]*[o]*[q]*[r]*[s]*[t]*[u]*[v]*[x]*[y]*[z]*' # regex that would match sub-strings. Just extend it up to z. 
>>> string = "bacde"
>>> for m in re.finditer(word, string):
...         words.append(m.group())
>>> print(words) # list of substrings
['b', 'acde']

Then you can extract the largest string from the list of strings 

>>> print(max(words, key=len))
acde
于 2017-06-08T19:25:34.540 回答