最长字母子串从哪里开始

Question

我正在研究麻省理工学院流行课程中的“最长字母子串”问题。我读过很多关于如何编码的信息，但我真的很难在概念上实现飞跃。之前的手指练习并不难。我想知道有没有人知道有没有什么材料可以真正地分解这个问题的解决方法。我试着拿出笔和纸，结果迷路了。我看到人们使用“计数器”之类的东西，或是包含“迄今为止最长的子字符串”的字符串，当我查看别人的解决方案时，我可以理解他们对自己的代码做了什么，但如果我试图合成我自己的东西，那就是没有点击。在

我甚至从课程中休息一下，试着通过其他一些书来学习，但我不断地回到这个问题上来，觉得我需要突破它。我想我正在努力的是从了解一些Python语法和工具到实际地使用这些工具来解决问题或“计算”。在

在任何人向我指出这一点之前，我已经了解了旨在帮助解决问题的课程材料。我看过一些助教制作的视频，这些视频有些帮助，但他并没有真正地将其分解。我觉得我需要和某人或类似的人配对编程。。。坐在白板前，让别人一步一步地走在我面前，回答我会提出的每一个愚蠢的问题。在

作为参考，问题如下：

Assume s is a string of lower case characters.

Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print

Longest substring in alphabetical order is: beggh

In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print

Longest substring in alphabetical order is: abc

我知道发布代码是有帮助的，但我没有其他地方没有的东西，因为，好吧，这就是我一直在我的IDE中玩的东西，看看我是否能理解发生了什么。同样，不要寻找代码片段-更多的阅读资料或资源，这些资料将扩展在这个问题中使用的逻辑。我会把我所拥有的东西贴出来，但它并不完整，在我开始感到困惑之前，我已经尽力了。在

s = 'azcbobobegghakl'

current = s[0]
longest = s[0]

for letter in range(0, len(s) -1):
    if s[letter + 1] >= s[letter]:
        current.append(s[letter + 1])
        if len(current) > len(longest):
            longest = current
        else:
            current = 

抱歉，格式错误，这还是新手。我对这个问题真的很失望。在

Answer 1

你的例子已经差不多了，只需要稍微调整一下

s = 'azcbobobegghakl'

longest = [s[0],]  # make them lists so we can manipulate them (unlike strings)
current = [s[0],]

for letter in range(0, len(s) -1):
    if s[letter + 1] >= s[letter]:
        current.append(s[letter + 1])
        if len(current) > len(longest):
            longest = current
    else:
        current = [s[letter+1],]  # reset current if we break an alphabetical chain

longest_string = ''.join(longest)  # turn out list back into a string

longest_string的输出：

^{pr2}$

Answer 2

如果您正在努力解决这个问题背后的概念和逻辑，我建议您退一步，看看更简单的编码教程和交互式练习。您可能还喜欢尝试JavaScript，从一开始就可以更容易地获得创造性，构建出可以在浏览器中立即与之交互的片段和/或网页。然后，当你在你的腰带下获得更多有趣的编码词汇时，它的算法部分就会显得更加熟悉和自然。我也认为让你自己的创造力和想象力引导你可以是一个非常强大的学习过程。在

让我们暂时忘掉字母顺序的部分。想象一下，我们有一袋信，我们一次抽出一个字母而不知道下一个字母是哪一个字母，我们必须连续记录R的最长运行。你会怎么做？让我们试着用文字来描述这个过程，然后是伪代码。在

我们将保留一个容器，以保存到目前为止我们所看到的最长的运行，另一个用于检查当前运行。我们提取字母，直到连续碰到两个R，然后将其放入“当前”容器中。下一个字母不是R，这意味着我们的运行结束了。“迄今为止最长的”运行是空的，因此我们将“当前”容器倒入其中并继续。接下来的四个字母不是Rs，所以我们忽略它们。然后我们得到一个R，我们把它放进“current”，然后是一个H。我们的跑步又结束了，但这一次我们在“当前”中的R比我们在“迄今为止最长的”中已有的两个还少，所以我们保持这些和空的“当前”

我们得到一个A，一个B，和一个C，然后运行五个R，我们将它们逐个放入“当前”容器中。我们的包现在包含最后一个字母，a T。我们看到我们的运行又结束了，而且“当前”容器的容器比“迄今为止最长的”容器多，所以我们倒出“最长”并用“当前”中的五个R替换其内容。就这样，我们在包中找到了R的最长行程。（如果我们有更多的运行，每次运行结束时，我们会选择是否替换“迄今为止最长”的内容。）

在伪代码中：

// Initialise
current <- nothing
longest <- nothing

for letter in bag:
  if letter == 'R':
    add 'R' to current
  else:
    if there are more letters
    in current than longest:
      empty longest and pour
      in letters from current
    otherwise:
      empty current to get ready
      for the next possible run

现在字母顺序的规定只是稍微使我们的情况复杂化了。我们将需要跟踪“current”中最近的一封信，为了继续运行，它没有看到另一个相同的字母。相反，下一个字母必须比我们放在current中的最后一个字母“更大”（按字典顺序）；否则，运行结束，我们根据“迄今为止最长的”进行数量检查

Answer 3

一般来说，从输入中创建所有可能性的列表，然后根据所需的附加逻辑过滤结果，这是比较容易的。例如，在查找最长的子字符串时，可以找到输入的所有子字符串，然后只保留有效序列的元素：

def is_valid(d):
  return all(d[i] <= d[i+1] for i in range(len(d)-1))

def longest_substring(s):
  substrings = list(filter(is_valid, [s[i:b] for i in range(len(s)) for b in range(len(s))]))
  max_length = len(max(substrings, key=len)) #this finds the length length of the longest valid substring, to be used if a tie is discovered
  return [i for i in substrings if len(i) == max_length][0]

l = [['abcbcd', 'abc'], ['azcbobobegghakl', 'beggh']]
for a, b in l:
  assert longest_substring(a) == b

print('all tests passed')

输出：

^{pr2}$