使用 ASCII 提取按字母顺序排序的最大长度子字符串

Question

请帮我解决这个问题。我是初学者，当我尝试切片和现在的 ASCII 时，这个练习让我发疯，这对我来说似乎更容易？如果它大于字符串中的前一个字符，我只能设法提取字符的 ord 值。如何从字母数组或至少它们的 ord 值中获取最大排序的子字符串？（代码应该拉：'fruw' 因为它最大排序）

s = 'gasgrerupxkgfruwgohfzl'
s2 = []
print s
for char in range(0, len(s)):
        if ord(s[char]) >= ord(s[char-1]):
            s2.append(str(ord(s[char])))
print s2

我的想法是否正确，或者我应该做哪些修改？谢谢

Answer 1

我只尝试并更改了您的代码

s = 'gasgrerupxkgfruwgohfzl'
s2 = ""                                      # a temporary string to hold value
temp = []                                    # added an extra array
print s
if s:
    for char in range(0, len(s)-1):
            if ord(s[char+1]) >= ord(s[char]):   # same as your code
                s2+=s[char]
            else:                                # if some letter is smaller, then add the previously longest str to temp array
                s2+=s[char]
                temp.append(s2)
                s2 = ""
    s2+=s[char+1]                                # As pointed out, the last letter would not have been detected as we loop up to len -1, thus we need to add this
    temp.append(s2)
    print max(temp,key = len)                    # print the longest string
else:
    print s

评论试图解释这些变化

Answer 2

因此，我们为跟踪您所在的索引付出了很多努力。直接迭代为 for x in y 更清晰。此外，无需为 s2 执行所有列表语法。只需将 s2 设为字符串即可。

s = 'gasgrerupxkgfruwgohfzl'
biglist = []
substring = s[0]  #this is going to get the first character
for char in s[1:]:   #loop over remaining characters
    if char > substring[-1]:   #if in order, add to end of string
        substring += char
    else:                     #if out of order, save what we have, start over
        biglist.append(substring)
        substring = char
biglist.append(substring)   #save the last thing

print biglist
    
print max(biglist, key = len)

输出是

['g', 'as', 'gr', 'eru', 'px', 'k', 'g', 'fruw', 'go', 'h', 'fz', 'l']

fruw

Answer 3

让我们先使用索引按照您的方式进行操作：

def solve(s):
    max_g = [] # this will store the final answer
    curr_g = [s[0]] # this list will store the contents of current group, start with first item. 
    for i in xrange(1, len(s)):
        c = s[i]
        # Now if the current character is greater than or equal to
        # last item in curr_g then simply append the current item to
        # curr_g
        # else compare the length of current_group with max_g
        # if it's greater than length of max_g then we have found a
        # new bigger group, so time to update value of max_g
        # and lastly update curr_g to [c]
        if c >= curr_g[-1]:
            curr_g.append(c)
        else:
            if len(curr_g) > len(max_g):
                max_g = curr_g
            curr_g = [c]

    #One last check of the group
    if curr_g and len(curr_g) > len(max_g):
        return ''.join(curr_g)
    else:
        return ''.join(max_g)

s = 'gasgrerupxkgfruwgohfzl'
print solve(s)
# fruw

使用生成器函数和 max 的更好方法。这一次只会在内存中存储一组：

def groups(s):
    it = iter(s)
    group = [next(it)]
    for c in it:
        if c >= group[-1]:
            group.append(c)
        else:
            yield ''.join(group)
            group = [c]
    if group:
        yield ''.join(group)

用法：

print max(groups(s), key=len)
# fruw

更新：

当然如果你想处理空字符串然后添加一个简单的if条件，即函数的顶部。而且由于您没有详细说明如何处理重复字符（实际上您也在答案中使用 >=），但是根据您的对另一个答案的判断，您想要的是一个简单的 >.

Answer 4

您可以尝试 izip_longest() 创建成对的相邻字符并在循环中比较它们：

from itertools import izip_longest

def longest_sorted_substring(s):
    longest = tmp = []
    for c1, c2 in izip_longest(s, s[1:]):
        tmp.append(c1)
        if c1 > c2:
            longest = max(tmp, longest, key=len)
            tmp = []
    return ''.join(longest)

>>> for s in 'gasgrerupxkgfruwgohfzl', '', 'a', 'ab', 'ba', 'acb', 'abdefgaooooooooozq', '123456780123456789abc0d':
...     print "Longest sorted substring of '{}' is '{}'".format(s, longest_sorted_substring(s))
... 
Longest sorted substring of 'gasgrerupxkgfruwgohfzl' is 'fruw'
Longest sorted substring of '' is ''
Longest sorted substring of 'a' is 'a'
Longest sorted substring of 'ab' is 'ab'
Longest sorted substring of 'ba' is 'a'
Longest sorted substring of 'acb' is 'ac'
Longest sorted substring of 'abdefgaooooooooozq' is 'aoooooooooz'
Longest sorted substring of '123456780123456789abc0d' is '0123456789abc'

请注意，使用 izip_longest() 是因为它处理最后一个字符而不添加特殊情况来处理字符串结尾。

Answer 5

这里有一个函数做同样的事情，对于任何必须使用您的代码的人（包括将来您自己）来说，阅读和理解它的作用要简单得多。

def find_lss(s):
    if not s:
        return s # empty s or None
    solutions = []
    current = None
    for char in s:
        if current is None or current[-1] > char:
            if current is not None: solutions.append(current)
            current = char
        else:
            current += char
    solutions.append(current)
    return max(solutions, key=len)

请注意，不需要使用 ord()，因为直接比较字符就可以解决您的问题。

然后你可以在你的例子中使用它：

>>> find_lss('gasgrerupxkgfruwgohfzl')
'fruw'

更重要的是，这个实现也适用于经典的极端情况，即空字符串：

>>> find_lss('')
''

它甚至适用于 None:

>>> find_lss(None)

（没有输出，也没有错误；即函数返回 None。）

使用 ASCII 提取按字母顺序排序的最大长度子字符串

Pull the max lengh substring sorted in alphabetical order using ASCII

python

string

ascii

substring