鱼C论坛Python精英挑战赛（第四季热身）

黑白色的枫

佩服15楼的兄弟

brankwong

# check the longest string in which every letter has no repeat.
def longest_substring(string):

    s=string
    length=len(s)
    s_head,s_len,max_s_head,max_s_len=0,1,0,1

    for i in range(1,length):
        if s[i] in s[s_head:i]:
            index=s[s_head:i].index(s[i])
            if s_len>max_s_len:
                max_s_head=s_head
                max_s_len=s_len           
            s_head=s_head+index+1
            s_len=s_len-index      
        else:
            s_len+=1

    if s_len>max_s_len:
        max_s_head=s_head
        max_s_len=s_len

    result=s[max_s_head:max_s_head+max_s_len]
    return result

brankwong

wyp02033 发表于 2017-11-21 15:42

输出结果是okay的，有一些循环没有必要，是否可以提高效率。

Cathaysian

def longest_substring(string):
    temporary, result = "", ""
    for char in string:
        if char not in temporary:
            temporary += char
        else:
            if len(result) < len(temporary):
                result = temporary
            temporary = ""
    if len(result) < len(temporary):
        result = temporary
    return result

之前发的少写了两行。


另外看了一下获胜的代码，这种题，O(n^2)也能获胜？实在是不敢苟同

jerryxjr1220

Cathaysian 发表于 2017-11-24 19:59
之前发的少写了两行。

所有在规定时间内递交的解答都是差不多两层嵌套的，没办法只能矮子里面拔高的。

brankwong

Bean_Wei 发表于 2017-11-23 14:26
# -*- coding: utf-8 -*-
# bulid by Bean_Wei

这里list.sort的语法似乎应该是：  list.sort(key=lambda x: len(x)),  仅供交流。

shigure_takimi

def longest_substring(string):
    length = len(string)
    subStrings = []
    for i in range(length-1):
        s = string[i]
        for j in range(i+1,length):
            if string[j] not in s:
                s += string[j]
            else:
                if s not in subStrings:
                    subStrings.append(s)
                break
    longestSubstring = subStrings[0]
    
    for subString in subStrings:
        if len(subString) > len(longestSubstring):
            longestSubstring = subString
    return longestSubstring, len(longestSubstring)
print(longest_substring('pwwkew'))

凌九霄

def longest_substring(string):
    lst, tmp = [], []

    for i in string:
        if i not in tmp:
            tmp.append(i)
        else:
            lst.append(tmp)
            tmp = []
            tmp.append(i)

    maxlenlst = list(map(len, lst))
    result = ''.join(lst[maxlenlst.index(max(maxlenlst))])

    return result,len(result)