0

给定一个字符串，找到最长的子字符串，其字符是连续的（即它们是连续的字母）但可能是混乱的（即无序的）。例如：
输入："owadcbjkl"
输出："adcb"
我们认为adcb它是连续的abcd。

（这是一个面试问题。）

我有一个使用 2 个条件运行 while 循环的想法，一个使用 Python 检查连续字符ord，另一个条件是找到最小值和最大值，并检查以下所有字符是否都在此范围内。

有没有什么办法可以用低运行时间复杂度来解决这个问题？我能做到的最好是 O(N^2) 其中 N 是输入字符串的长度，并且ord()似乎是一个缓慢的操作。

4

1 回答 1

4

如果子字符串定义为''.join(sorted(substr)) in alphabetthen：

  • 子字符串中没有重复项，因此最长子字符串的大小小于（或等于）字母表的大小

  • (ord(max(substr)) - ord(min(substr)) + 1) == len(substr), 其中 ord()返回字母表中的位置（+/- 常量）（内置 ord()可用于小写 ascii 字母）

这是O(n*m*m)-time, O(m)-space 解决方案，其中nislen(input_string)和mis len(alphabet)：

from itertools import count

def longest_substr(input_string):
    maxsubstr = input_string[0:0] # empty slice (to accept subclasses of str)
    for start in range(len(input_string)): # O(n)
        for end in count(start + len(maxsubstr) + 1): # O(m)
            substr = input_string[start:end] # O(m)
            if len(set(substr)) != (end - start): # found duplicates or EOS
                break
            if (ord(max(substr)) - ord(min(substr)) + 1) == len(substr):
                maxsubstr = substr
    return maxsubstr

例子：

print(longest_substr("owadcbjkl"))
# -> adcb
于 2013-03-26T07:39:24.207 回答