0

文字列を指定して、文字が連続している（つまり、連続した文字である）が、乱雑になっている（つまり、順序が狂っている）最長の部分文字列を見つけます。例：
入力："owadcbjkl"
出力：形成されるのと同じくらい連続している"adcb"
と見なします。adcbabcd

（これは面接の質問です。）

Pythonを使用して連続文字をチェックするord条件と最小値と最大値を見つけて次のすべての文字がこの範囲内にあるかどうかを確認する条件の2つの条件でwhileループを実行することを考えています。

実行時間の複雑さを低く抑えてこの問題を解決する方法はありますか？私が達成できる最善の方法はO（N ^ 2）です。ここで、Nは入力文字列の長さであり、ord()動作が遅いようです。

4

1 に答える 1

4

サブストリングが次のように定義されている''.join(sorted(substr)) in alphabet場合：

  • 部分文字列に重複がないため、最長の部分文字列のサイズはアルファベットのサイズよりも小さい（または等しい）

  • (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 に答える