2

EDIT :同様のタスクに関する質問が SO で既に行われていることは承知していますが、この特定のコードの問題を見つけることに興味があります。また、この問題は再帰を使用せずに解決できることも認識しています。

タスクは、文字がアルファベット順に出現する最長の部分文字列を検索 (および出力) するプログラムを作成することです。同じ長さのシーケンスが複数見つかった場合は、最初のシーケンスが出力されます。たとえば、文字列の出力は にabczabcdなりますabcz。

私は手動テストに合格したように見える再帰でこの問題を解決しました。しかし、ランダムな文字列を生成する自動テスト セットを実行すると、出力が正しくない場合があることに気付きました。例えば：

の場合s = 'hixwluvyhzzzdgd'、出力はhix代わりにluvy

の場合s = 'eseoojlsuai'、出力はeoo代わりにjlsu

の場合s = 'drurotsxjehlwfwgygygxz'、出力はdru代わりにehlw

しばらく苦労した後、これらの文字列の何が特別で、バグの原因なのかを理解できませんでした。

これは私のコードです:

pos = 0
maxLen = 0
startPos = 0
endPos = 0


def last_pos(pos):
    if pos < (len(s) - 1):
        if s[pos + 1] >= s[pos]:
            pos += 1
            if pos == len(s)-1:
                return len(s)
            else:
                return last_pos(pos)
        return pos


for i in range(len(s)):
    if last_pos(i+1) != None:
        diff = last_pos(i) - i
    if diff - 1 > maxLen:
        maxLen = diff
        startPos = i
        endPos = startPos + diff

print s[startPos:endPos+1]
4

17 に答える 17

3

ここ。これはあなたが望むことをします。1 回のパスで、再帰は必要ありません。

def find_longest_substring_in_alphabetical_order(s):
    groups = []
    cur_longest = ''
    prev_char = ''
    for c in s.lower():
        if prev_char and c < prev_char:
            groups.append(cur_longest)
            cur_longest = c
        else:
            cur_longest += c
        prev_char = c
    return max(groups, key=len) if groups else s

それを使用して：

>>> find_longest_substring_in_alphabetical_order('hixwluvyhzzzdgd')
'luvy'
>>> find_longest_substring_in_alphabetical_order('eseoojlsuai')
'jlsu'
>>> find_longest_substring_in_alphabetical_order('drurotsxjehlwfwgygygxz')
'ehlw'

注：おそらく奇妙な文字で壊れるでしょう。提案された入力でのみテストされています。これは「宿題」の質問なので、解決策をそのままにしておきますが、まだ最適化を行う必要がありますが、少し理解できるようにしたかったのです。

于 2013-10-27T13:36:34.643 に答える
2

ネストされたforループ、スライス、およびsorted. 文字列がすべて小文字ではない場合は、 を使用して比較する前に、部分文字列を小文字に変換できますstr.lower。

def solve(strs):
  maxx = ''
  for i in xrange(len(strs)):
      for j in xrange(i+1, len(strs)):
          s = strs[i:j+1]
          if ''.join(sorted(s)) == s:
              maxx = max(maxx, s, key=len)
          else:
              break
  return maxx

出力：

>>> solve('hixwluvyhzzzdgd')
'luvy'
>>> solve('eseoojlsuai')
'jlsu'
>>> solve('drurotsxjehlwfwgygygxz')
'ehlw'
于 2013-10-27T13:42:30.223 に答える
0

より多くのループがありますが、それで仕事は完了します

s = raw_input("Enter string")
fin=""
s_pos =0
while s_pos < len(s):
    n=1
    lng=" "
    for c in s[s_pos:]:
        if c >= lng[n-1]:
            lng+=c
            n+=1
        else :
            break
    if len(lng) > len(fin):
        fin= lng`enter code here`
    s_pos+=1    
print "Longest string: " + fin
于 2015-06-21T15:44:42.557 に答える
0

これは、EDX 上の CS6.00.1x の問題セットの質問だと思います。これが私が思いついたものです。

s = raw_input("Enter the string: ")
longest_sub = ""
last_longest = ""
for i in range(len(s)):
    if len(last_longest) > 0:
        if last_longest[-1] <= s[i]:
            last_longest += s[i]
        else:
            last_longest = s[i]
    else:
        last_longest = s[i]
    if len(last_longest) > len(longest_sub):
        longest_sub = last_longest
print(longest_sub)
于 2016-11-08T03:00:34.010 に答える
0

シンプルでわかりやすい:

s = "abcbcd"    #The original string

l = len(s)    #The length of the original string

maxlenstr = s[0]    #maximum length sub-string, taking the first letter of original string as value.

curlenstr = s[0]    #current length sub-string, taking the first letter of original string as value.

for i in range(1,l):    #in range, the l is not counted. 

    if s[i] >= s[i-1]:    #If current letter is greater or equal to previous letter,
        curlenstr += s[i] #add the current letter to current length sub-string
    else:        
        curlenstr = s[i]  #otherwise, take the current letter as current length sub-string

    if len(curlenstr) > len(maxlenstr): #if current cub-string's length is greater than max one,
            maxlenstr = curlenstr;      #take current one as max one.

print("Longest substring in alphabetical order is:", maxlenstr)
于 2016-09-23T10:03:08.113 に答える
0 
def find_longest_order():
`enter code here`arr = []
`enter code here`now_long = ''
    prev_char = ''
    for char in s.lower():
        if prev_char and char < prev_char:
            arr.append(now_long)
            now_long = char
        else:
            now_long += char
        prev_char = char
    if len(now_long) == len(s):
        return now_long
    else:   
        return max(arr, key=len)

def main():
    print 'Longest substring in alphabetical order is: ' + find_longest_order()

main()
于 2015-06-23T03:24:50.187 に答える