最长连续字母序列

Question

最长连续字母序列

3

假设我有一个小写字母字符串，例如：

'ablccmdnneofffpg'

我的目标是找到字符串中连续数字的最长序列，本例中为：

'abcdefg'

直觉上，我们可以找到每个字母的循环并获取从该字母开始的最长序列。一个可能的解决方案是：

longest_length = 0
start = None
current_start = 0
while current_start < len(word) - longest_length:
    current_length = 1
    last_in_sequence = ord(word[current_start])
    for i in range(current_start + 1, len(word)):
        if ord(word[i]) - last_in_sequence == 1:
            current_length += 1
            last_in_sequence = ord(word[i])
    if current_length > longest_length:
        longest_length = current_length
        start = current_start
    while (current_start < len(word) - 1 and
           ord(word[current_start + 1]) - ord(word[current_start]) == 1):
        current_start += 1
    current_start += 1

还有其他更少行数的解决问题的方法吗？或者甚至可以使用一些Pythonic方法吗？

- Peter

2

你想要找到“最长序列”还是这样一个序列的“长度”？ - John Gordon

你的算法使用了CPU周期。你可以同时跟踪所有可能的序列，然后只迭代一次，以内存换取CPU。 - Harvey

4个回答

1

一种通过牺牲内存来换取时间的解决方案：

它会跟踪所有出现的序列，然后在结束时打印找到的最长序列（尽管可能不止一个）。

from contextlib import suppress


class Sequence:
    def __init__(self, letters=''):
        self.letters = letters
        self.last = self._next_letter(letters[-1:])

    def append(self, letter):
        self.letters += letter
        self.last = self._next_letter(letter)

    def _next_letter(self, letter):
        with suppress(TypeError):
            return chr(ord(letter) + 1)
        return 'a'

    def __repr__(self):
        return 'Sequence({}, {})'.format(repr(self.letters),
                                         repr(self.last))


word = 'ablccmdnneofffpg'
sequences = []
for letter in word:
    for s in sequences:
        if s.last == letter:
            s.append(letter)
            break
    else:
        sequences.append(Sequence(letters=letter))

sequences = list(sorted(sequences, key=lambda s: len(s.letters), reverse=True))
print(sequences[0].letters)

- Harvey

0

与MosesKoledoye的解决方案类似，但仅存储字符序数的长度，并在最后构建解决方案字符串。因此，这应该更节省空间：

def longest_seq(s):
  d = {}
  for c in s:
    c, prev_c = ord(c), ord(c) - 1
    d[c] = max(d.get(c, 0), d.pop(prev_c, 0) + 1)
  c, l = max(d.items(), key=lambda i: i[1])
  return ''.join(map(chr, range(c-l+1, c+1)))

- user2390182

0

你基本上是在寻找“最长递增子序列”，这是一个经过深入研究的问题。可以在维基百科中查看伪代码。

- user2722968

1

不完全正确。abfh是一个递增子序列，但不满足OP的条件，即它必须由连续字母组成。另一方面，它显然与“最长递增子序列”问题有关，相应的算法可以针对这个问题进行调整。 - John Coleman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Moses Koledoye · Accepted Answer

你可以使用字典来追踪字符串中出现的连续字符子序列，并选择长度最长的那个。每个子序列都以字母表中的下一个候选字母作为关键字，这样一旦在字符串中找到了预期的候选字母，就会用它来更新相应的子序列字典值，并作为新的字典值添加，以字母表中的下一个字母作为关键字。

def longest_sequence(s):
    d = {}
    for x in s:
       if x in d:
           d[chr(ord(x)+1)] = d[x] + x
       else:
           d[chr(ord(x)+1)] = x
    return max(d.values(), key=len)

print(longest_sequence('ablccmdnneofffpg'))
# abcdefg
print(longest_sequence('ba'))
# b
print(longest_sequence('sblccmtdnneofffpgtuyvgmmwwwtxjyuuz'))
# stuvwxyz