连续字母的最长序列

假设我有一串小写字母，例如：连续字母的最长序列

'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方法？

来源

2017-06-04 Peter

你想查找_longest sequence_或这样一个序列的_length_吗？ –

你的算法使用cpu周期。你可以一次追踪所有可能的序列，然后只需要为cpu交易内存就迭代一次。 – Harvey

您可以使用字典来跟踪连续字符的所有子串，如字符串中所示，然后取最长的字符串。

每个子是由字母下一个候选键这样，一旦在字符串中达到了预期的候选者，它被用来更新在字典中的相应序列的价值，并添加新的字典值由下一个字母键：

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

来源

2017-06-04 15:57:13

@DSM更新。在''ba“上测试（给出''b''或''a';订单可以用'OrderedDict'来修复）和其他主机。 –

看起来它会起作用。 :-) – DSM

好的解决方案，当我看到问题时采用了相同的方法。 'max（v for v in d.values（））'与max（d.values（））'相同，btw。 – schwobaseggl

你基本上是问的longest increasing subsequence，这是一个精心研究的问题。查看维基百科中的pseudo code。

来源

2017-06-04 17:11:15 user2722968

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

该交易存储器（部分的）时间的溶液：

它跟踪看到的所有序列，然后在结束打印最长实测值（尽管可能有不止一个）。

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)

来源

2017-06-04 18:10:31 Harvey

到MosesKoledoye's的解决方案类似，但只存储了字符的序数的lengthes，只有竣工图中端解决方案的字符串。因此这应该更具有空间效率：

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

来源

2017-06-04 19:44:28 schwobaseggl

连续字母的最长序列

回答

相关问题